[Giaguara]

From your AddressBook backup, or from your Time Machine or other backup.

Or from your other device that has them all still, or from your .mac/me service that could have them all.

I once lost EVERY single US format phone number I had in my AddressBook, and every single contact that contained them. That was not fun to try to recover.
After that incident, before I do any sync with it, or even without, at least once a month I use the backup option. AddressBook > File > Edit > Export > Address Book Archive...
While some contacts may be recoverable exporting them from other services (LinkedIn, Facebook etc, whatever you use) they would not contain them all.
Good luck.