If possible I try to add contacts through gmail on line. It can be done on the phone but each one saves contacts a bit differently (I'm talking android models).
Make sure he's sync to gmail I'm not sure how contacts are added in the Incredible but it shouldn't just be randomly deleting them unless he's entering them in incorrectly.