How do I REALLY sync ALL contacts to a new phone
As you've already figured, a built-in solution is:


Open the contacts app on the "old device"
In Menu → Import/Export, chose to export
Copy the resulting 0001.vcf file to your "new device"
On the new device, open the contacts app and chose to "import" from Menu → Import/Export


Hint: take care there's enough free space available on the "exporting" device (file might get large, as contact pictures are stored inside it as well). You might not always get a warning when storage runs full, but instead end up with some "incomplete export", which then cannot be imported on the other end.



Now for the second part: why didn't they sync automatically? First, there are a few different "storages" to be considered:


On SIM
Google Contacts


These two are available on all devices. Depending on device and ROM, there might be additional "storages", e.g.


Exchange
PC Suite


Assuming you're speaking of Google's sync: That only takes care for Google contacts. As the PC Suite would only cater contacts in PC Suite to sync them with its desktop counterpart, and Exchange would not care for anything but Exchange contacts (you wouldn't want your personal contacts appearing in your company's address books, would you?). SIM contacts are a very special case: Nothing cares to sync them anywhere. I'm not even sure whether Import/Export is touching them.

So as parts of your contacts have been stored as "LG PC Suite contacts", these have not been sync'd with Google (and your "Google contacts" not with LG Suite), which explains the miss.