They get the list of people from the online status and then send PMs to them.
It's the most efficient way to do it, rather than going through the long member list, where 80% of accounts have never posted and 90% of them haven't logged in in a long time and probably won't log in again.
I'm online a lot (unfortunately ) and I never get these messages. Others that I have advised to turn off online status also don't get these messages anymore. I'm 99% certain that's how at least some of the scammers do it.
I know that's how they operate with the forum PM's ... so maybe they look at the online list on the forums and then use that to determine which users to message on the main site. However, most people have different usernames here on the forums than they do on the main site, so I'm not sure how the scammers operate...