Ok, I have seen this question many many times... and I thought I would share my experience and solution.
No matter how many times I deleted the user, cleared PIM backups, re-sent Service books, moved my contacts in the mailbox to a different folder, which would remove them on the bb, but as soon as i moved what appeared to be single entries back, when they syncd with the bb, they would double up etc. I would get duplicate entries in the address book EVERY time... but the dups were not showing up in Outlook... everything pointed to the BES (4.1) server for sure... BUT there was in fact nothing wrong with the BES, or the 8830 at all!
Initially, I changed everything over to a new exchange/bes server... i didn't move anything but PST's and setup everything new... the problem was when i got lazy on the user's workstation changing to the new domain, i used the File and Settings Transfer Wizard to save their settings, logged them onto the new domain, and restored the settings... .well, this brought over the outlook profiles, etc. from the old domain... in a hurry to get the user up and running, i just changed the server name in their outlook profile... everything supposedly seemed to work fine... however, outlook 2003 started complaining about having to open in compatibility mode... .this was what keyed me that something was wrong... looking at additional posts, the .ost seemed to be corrupted, but i deleted it and still no satisfaction.
Finally, I simply deleted the outlook profile and created a brand new one and BAM!!! Outlook showed duplicate entries for everything... evidently the ost and the profile were corrupt and had stacked/layered contacts that were not visible in outlook under the old profile.
I deleted the duplicates in outlook and ALL WAS WELL! Another issue to overcome was deleteing over 400 duplicate entries... i found this helpful post: Easy Free Way To Remove Duplicate Contacts From Microsoft Outlook
I hope this easy fix helps some of you and saves you hours of trials and tribulations unlike myself, because I spent hours and hours looking far and wide for complicated problems with BB software or hardware to no avail... this simple answer didn't seem to be ANYWHERE!!