Oops, you're right.
I have no time to test it myself right now, but if you disabled it for Everyone (and Members), unapproved users should not be able to use it. Did you check if the unapproved user is not in another group, which has permissions? Maybe some of your plugins moved him there.
Huh, I get a free test instance from Woltlab. https://e0d007.woltlab-demo.com/ (demo / 6hpdtxzv7p )
Test account (unapproved - test / test1234 ) can use PM.
After activation he can't.