Are you as well doing contact sync to the local names.nsf.  One suggestion is to get all the copies in sync one time.  I would make sure you backup all the contacts into a blank db from the users mail file..   From the mail file I would cut and paste the contacts in. Now you have unique unid.  Let replication happen to all the local replica copies of the mail file  and to the mobile device.   If you are  doing contact sync to the local names.nsf I would backup and delete the contacts in the local anmes.nsf and turn on contact sync to run on a schedulle.   With so many places that the user can change /add/delete a contact you need to instruct them to really pick a "master" and need to insure replication happens on a scheduled basis.

Thanks for reply,

I contacted support to raise a PMR

Think what I was told

1. Disable the Notes contact sync on all stations

2. Stop Traveler

3. clear out the users contacts from the server ($contacts)

4. Clear the deletion stubs on server DB

5. Re-import the contacts into the server db.

OK this worked I saw the contacts go in properly. Then after 24 day they disappeared.

Like what they told you to do was what I said to do.   When you did the import it created new documents get new unids so it was not replication that is the issue since even if there was a copy with old deletion stubs it would delete the old doc not the newly imported docs.   How about ruling out traveler and see if the docs get deleted after a 24 hour cycle.

Not sure why they wanted you to clear the deletion stubs.   You want that to replicate around and only have the new documents from the reimport to be there.