I just realized I had some new PM's but was not aware of them before because My Home page did not say "new Pm's".
Daeljan said he had this problem too, so I'm assuming everyone is.

And I'm still unable to delete them.

have you tried logging out, then back in?

yes and I cleared the browser and logged back in, still no new message notification

I don't get new mail notifications and I can't delete any old mails either since a long long time ago...

Please let me know whether any of these problems are still cropping up...
Fairly sure all the problems listed should be fine now.