Yeah, I really cringed when I typed that answer, but at this point, it is damn near impossible to tell one way or another.
If there were a way to export the contacts in your phone to a CSV file then it'd be a lot easier, as you could use something like WinDiff on your computer to compare that file with an export of your contacts in GMail / Google, but I don't know of a way to export the contacts on your phone, unless ....
Doh!!!
Listables! v0.2.2 Application for Android | Tools, by our very own ALostPacket! I'm such an idiot for forgetting that! Since that will allow you to save your contacts in CSV format, and in your GMail you can export your contacts, also in CSV format, you can then load up your favorite differencing program (I personally use WinMerge) you could then easily see which lines were missing from one file to the other....