I think there should be an option to automatically delete old messages if you run out of room or at least be able to retrieve old messages that you phone doesn't give you because its too full. Who could we talk to about that?
My wife had this issue and when she finally visited a Verizon store, they found she had over 5,000 emails in her trash bin. It turns out when you delete an email through the phone, it ends up in trash, but trash needs to be deleted also. Quite a pain, because there is no way to "empty" the trash folder, and you must select every email and then delete it again.