[GnatGoSplat]

There is no way to recover your Contacts on the PDA-side. They're gone forever.

If you are using Vista, there may be some hope to recover your Contacts on the PC side. Go look for your outlook .pst file (I'm not sure where it normally lives since I use Exchange). Once you find it, right click and go to "Restore previous version". Choose a date when your contacts existed, and click the "Restore" button. Everything will then be fine from that point.

Many people may not like Vista, but I have found one huge compelling reason to use it: Restore previous version. That feature has saved my *** more times than I'd like to admit.