I think that I just figued out what is going on here. I had been having the problem too and just did some content and photo edits on my site (www.ParadiseLakesCondo.net). While I was doing the updates, I noticed that the Contact Us object has changed slightly and now includes a checkbox at the bottom of the object for "I want to receive newsletters, udpates and special offers". By default the box is unchecked.
I ran a quick experiment and used my contact us page for 2 different test users, checking the box for User 1 and leaving it blank for User 2. User 1 was automatically added to my Contacts while User 2 was not. So it is not a bug, it is new functionality that MSFT added to the Contact Us object.
Now if we could just get them to default the box to checked instead of unchecked, life would be good.
Roger...