I had the same problem with one of my users. He was unable to delete messages from a specific day. He was able to delete all the messages, but not from that one day. I had to wipe his handheld, update the os and then redo the EA. It worked fine after that.