What may have caused losing 5-30 of our two iPhone4's contacts without using iCloud or any other sync?
If you go into your Contacts app, select Groups in the top left corner and click on All Contacts -- do they show there? The phone only caches a certain amount of addresses and you may need to manually select lesser known Contacts if they get purged from the cache.