Over the air sync with Exchange? That's should be safe. Sync or imports offer the most chances for screw-ups - even so, it's very rare that there are problems. Most problems are user error - for example, you edit a CSV and move a column up. Macros are another area where users can make mistakes that mess up their contacts.
Are they messed up on the phone and in outlook? If just in outlook, try resetting the view.