Google giving different results for searches with/without common words

"example" is a very common keyword and was not included in your search

[ALbino]

We had a referral today from Google that was "keyword & keyword". I went to look at this on Google and we come up #3. At the top of the page though it says:

""&" is a very common word and was not included in your search"

Just for fun I tried the search "keyword keyword" without the "&" and the results were completely different with us coming up on the second page at #14. Also there were 40 less results without the "&" (out of over 6,000).

I'm not complaining mind you, I just find it interesting that the "&" is in fact not ignored at all and is apparently fairly important to the rankings. Anybody else experience something similar?