Where exactly does Android get its contact suggestions from? I have a phone right here (Evo 3D), it has no service (except my wifi) and I've only added an obligatory gmail account which has one contact.

No Facebook, no Google+, no Twitter, etc.

Yet I got a "matched contact suggestion" notification. What is that? Where did it come from?

My main phone (TMO G2) with all of the services never gets these things and I'm not familiar with that at all.

Insight appreciated.
As long as your WIFI has internet connectivity, Android will be able to communicate with Google's servers.

There is one thing that people get wrong when it comes down to contact suggestions, be it Facebook or Google: They imply that they are the only ones that have saved the contact somewhere. But it's also the other way round. Which means that, the contact that was suggested to you has most likely your gmail e-mail address saved in his address book.