Google, Bing and Yahoo all have different search bots for mobile. Google’s recommendations on how to make sites mobile friendly are all based around building separate sites and then ensuring that the Google mobile bot is redirected to the mobile version. Matt Cutts has talked about this in a video answer and Google has gone so far as to describe how you should redirect the Google mobile bot in some detail.
What does this mean for sites using responsive web design? Honestly, I don’t know. Nor does anyone else it appears. There is some question about whether or not mobile SEO is even worth pursuing.
But it is worrisome. Google recently announced that mobile website optimization now factors into mobile search ads quality. I’ve seen no indication that Google is considering responsive web design in its definition of mobile optimization. The announcement linked to several case studies and articles illustrating separate sites as the approach.
This is probably a problem with the search engines and not with responsive web design as a technique, but if a company relies on search engine traffic for revenue, it likely won’t matter who is to blame.