I have had this same problem since I got the phone when it came out - so 3.0 and 3.1. I can be standing in the same spot and the third call will come through. VM will register about 2-4 hours later if they leave a message but a missed call will never show up. I have talked to Apple and AT&T who all seem to tell me that since no call is registering then no one is really calling me. Quite helpful- NOT.