Actually, it is NOT because of the new layout. This problem popped up at least a year ago, with one of the earlier "upgrades". Previously, a moderator could tell if someone was a paid member even if they hadn't upgraded their user group. All we had to do was look at their profile, and if it showed PM, we knew they were paid. Then the software started showing everyone with PM, even if they didn't actually have access to them.
The best bet is to go to email, and insist that everyone who deals with you activate their email. Everyone has email, and unlike Visitor Messages, it is private.
Settings > My Account > General Settings
Messaging & Notification
Receive Email from Administrators
Receive Email from Other Members
Receive Friendship Request Email