Do you think it might be an idea to send the recipient an email alert when they receive a PM?
I don't generally check if I have PMs and it's not very noticeable that one has arrived if you are not expecting it.
In the same way, I don't have faith that somebody I send a pm to will notice it either. So I post on the forum that I've pm'd them because I know that that will generate an email. But that sort of defeats the purpose of the message being private, so it's not ideal.
I think that would be great, especially for "newbies", who probably need to see them the most. From a phone, you have to actively search them out. There is no obvious notice until you check your profile.