Actually - before you look at anything, I think the issue might be to do with how many mail shots get sent.
For example, if a search returns 400 people and those emails get spread out at 8 emails per minute, and a second search is carried out straight afterwards, also returning 400 people, will that essentially mean that 16 emails are being sent per hour, or would the 800 emails still be spread out at a rate of 8 per minute?
Update on this - I've established from the hosting company that emails are being spaced out, so it looks like I just need to tweak the settings, and make sure the site owners know not to go mad and try to send out thousands of emails.