Admins, are you guys using IP.Board's personal messenger throttle option at all? It sounds like a draconian measure, but if you're not using it, throttling down to like a message every two or three minutes maximum would be something nearly no legitimate poster would even notice, but would make things less than ideal for spammers.
Edit: OH! And throttling searches to once every ten seconds or so would save you piles of bandwidth (and therefore $$). Noticed you guys don't do that.
I actually just ratcheted that down a bit late last week---will go further if this persists. We also limit the number of individuals one can invite to a PM, so someone cannot blast out to more than a few people at a time.
Looks like we also have search flood control in place as well. Is it not working for you?