The contacts are not stored locally in the clients, they're stored in the IM&P server in the DB, and then the clients pull the info from there.
I'd make sure that you see the contacts in the IM&P DB when you create them, and make sure they're still there the next day to determine where the issue might be.
HTH
java
if this helps, please rate