Are you using Mobile Me or iCloud? MobileMe was shut down a bit ago and iCloud should have solved thses issues for you. Did they?
One way to easily force a resync of all of your devices to the Contacts/Address book database that is in the cloud is to enter a new test address using each device. I call thenm iPad. iPhone and iMac, entering each from the respective dvice. They shoudl each appear instantly on all the other devices. If they do not, you can easily tell which one's iCloud sync is misbehaving.
BEFORE PROCEEDING, BACK UP THE MISBEHAVING DEVICE'S CONTENTS!
Go the iCloud settings for that device, use the sign out button. The warnings you will see are scary but harmless. However, you push these buttons at your own risk.
Wait a few minutes, sign back in top iCloud using your Apple ID and password. This forces a reload of the contacts database form the iCloud storage and all of your devices should now display the same contacts database.
This has worked for me on two separate accounts, mine and a coworker's. Doesn't mean it will work for you. Doesn't mean you know what you're doing or that it is a harmless suggestion.