Ok, the situation has changed slightly:

I now see lots of 513s in my logs, relaying denied, so I am wondering if removing my ip from the smtpaccess file was the culprit?

Anyway, now when I try to send mail to any other email address but mine (e.g. soan...@hotmail.com) from work, which is not my localhost, it will not relay. Does this mean that for every user that is a remote user I have to add their IP to the smtpaccess file to allow them to send email?

(If any are wondering I changed my smtp host at work to my work smtp server, otherwise these emails would not have reached you all!) :D

Thanks!