I believe Trust Tier #1 is required to send personal messages, unless the settings may have been changed for that. If it’s possible to adjust that to a higher tier I would recommend that as a first step.
Otherwise that may be a feature request to notify a moderator or administrator if many messages are being sent by a new user, that may be possible to do that.
Users at trust level 0 cannot …
- Send personal messages to other users*
Although the chat system may have different requirements than the messages.
Also you could implement a policy similar to the one here at Meta that any kind of marketplace solicitations must be made in a public forum post, not messages. Then most likely you would be notified earlier about there is that kind of spam/scam activity occuring.