That particular open relay test (the nobody% one) can produce a false positive. Basically it looks like it's going through from the other end because of the way Qmail treats the percent symbol, but the mail won't really go to the address they're trying to spam. It'll all end up going to whatever default address you have the server set up to send undeliverable mail to if you have one set up. Otherwise it goes off into /null never to appear again.
As far as getting rid of your open relay for normal email if you indeed have one, it kinda depends upon what you need to do and what capabilities your clients using email on your server have. If you can simply get away with closing the relay totally you can log into your Plesk GUI, click on the Server Button, click on the Mail button and put a mark in the "Closed" radio button under the Relaying area and you're basically done. If memory serves, I think that is the default setting Plesk/Qmail comes with.
The trick comes in if you do need to allow relaying for clients who have POP3 accounts on your server (I have to do this this because I have some clients whose ISP's don't allow them to smtp through their account and have their actual domain name in the From or Return fields.) If you do need to allow your clients to relay I'd suggest selecting the Authorization Is Required radio button and also checking the SMTP box. What that does in a nutshell is tell the server to require a valid username/password pair from anyone trying to send mail through Outlook/Eudora and the like before it allows them to send anything. That still keeps the spammers at bay since they won't have that authentication information. If you use this method you'll have to tell all of your clients that they need to configure their email software to "Allow Authentication". Otherwise they'll be able to get their mail from the server but not send any. Just so that you know immediately what to tell them if you make that change and they suddenly start complaining that they can receive but not send any email.
If you're going to use this method you'll want to make sure of a couple of things... First, be careful about what IP addresses/mask combos you have in the Whitelist on that same Plesk GUI page as above. In order for scripts on the server to be able to send email you'll have to whitelist 127.0.0.1, however make very sure you only have a mask of 32 (you might be able to get away with a mask of 24 and still keep the spammers at bay, but I wouldn't personally). So the only thing you want to add to that section if you have scripts sending mail is 127.0.0.1 / 32 If you have much more than that single 127 entry your server will be wide open to the spammers.
The second thing to be very sure of is that you have something in your rcpthosts file. On the Plesk Standard install that should be located at /usr/local/psa/qmail/control/rcpthosts when you ssh into the server. That file should be automatically created by Plesk and should contain all of the domains being hosted on your server. So by default it should be just fine unless you've done some tinkering. However if for some reason this file is blank you would again be opening your server up to accept all relay requests, even if you had a closed relay or authentication set on the Plesk GUI side of things.
As far as the IP's and messages you're seeing in your /var/log/secure file I wouldn't worry about that too much as long as you're not seeing the mail actually being sent in your /var/log/maillog file. Even if your server/relaying is secure you're going to see those smtp connection attempts constantly in this file (the key word there being "attempts", meaning they're trying to use you to send their spam, but that doesn't necessarily mean they're being successful.) Any mail sent by any email software, php, asp, cgi or fp script should show up in your maillog. I generally keep 3 ssh sessions open if I suspect something and watch tail -f on /var/log/maillog, /var/log/messages and /var/log/secure so that I can see what's actually happening. Secure shows who's trying to connect to what. Messages will give me an authpsa line with the IP when someone actually connects (with my setup I get a line which says something like "authpsa: IMAP connect from@ [IP.Number]". And maillog tells me anytime email goes out. Then if I do see something funny but it's
not coming from a normal email transaction I can also check the time frame it happened against /usr/local/psa/apache/logs/access_logs to see what pages were being accessed on the server at that time. It's not the easiest thing in the world to track down a runaway script, but it can be done. Also if I see the same IP number attempting to spam over and over again in /var/log/secure I've been known to just add that IP to my firewall rules and block them from the server totally.
As to Matt's FormMail script, tell the client who is using that thing that they need to upgrade to Matt's latest version which has only been out about a year now. The new version does some checking for the referring page's url and also allows you to configure where mail can be sent if it's going off of that domain. It's much more secure than the old version, which had a huge hole in it. They should know this and have upgraded, but many don't. Personally I don't even use it anymore myself. I have a little php script which does the same thing I use and advise my clients to use just because it's easier for them to configure and is also easier on the server resources IMHO.
Hope I didn't ramble too much there. 
Maybe you'll be able to glean something useful from all of that...
Squire
