Hardware firewall advice needed


Not sure it this is posted in the correct forum? Mod's please move it if you want.

I'm running 10.4.2 server as our company mail server. The problem is we keep getting used as an open relay for other people. I have installed Netbarrier X3 an configued it as a client/Server but as soon as SMTP is enabled someone still gets through. I have cheked our IP on some of these open relay check web sites and we come up clear. The most recent viloation was an email someone received masking as an Ebay Account Confirmation mail asking for peoples account details. the mail is masked by a link in the email with our server IP at the front of the URL (http://OUR.IP/.signin.ebay.com/ws/eBayISAPIdllSignIn.php).
I'm told the only way to stop this is to use a hardware firewall. I need advice on what to get . I do not want to spend a fortune to find out it's the wrong thing and does not stop this Open Relaying.

Any advice welcome