Scott,
Mine are working fine.
If you scroll down to the bottom of any of your message folders (sent or inbox) you will see a status bar like the one below. By any chance do you have more than 500 total messages? Maybe once you get over 500 it won't save any more?
Folder Controls
Sent Items contains 217 messages. You have 314 messages stored, of a total 500 allowed. (Empty Folder)