Permalinks set to /%postname%/ but still have links being indexed in the form ?p=x

There are two places bots would look: your sitemap (if you submitted one to google), and your robots.txt. WordPress itself doesn’t put anything in robots.txt (unless you set your site to private, then it tells the bots not to index anything), nor does it create xml sitemaps that google would use.

There are a few plugins that will do this for you, though. I know Google XML Sitemaps is popular, and works for me. Yoast’s SEO plugin also creates sitemaps for you.

I think the easiest way to get Google to start indexing correctly is to create a sitemap with one of those two plugins and then submit it to google using google webmaster tools.