ASMTP Relaying Fails

[#1]

We have ASMTP setup on a Plusnet account, and use it to send mail from *anywhere*. From some locations (and only some, not all), we are unable to send mail, and get the message
Your message did not reach some or all of the intended recipients.

      Subject:            FW: email issue
      Sent:                25/07/2011 14:18
The following recipient(s) could not be reached:
      'Tony Brown' on 25/07/2011 14:18
            550 5.7.1 Relaying denied
We suspect this may be due to some hotel ISPs not allowing Port 25 access. Is this likely to be the problem? Is there any workaround for this?

[#2]

I know that some mobile providers restrict access, it's not unlikely that hotels may do similar. We don't restrict authenticated SMTP access so it must be the connection not reaching our outgoing server in the first place in which case it will in all probability be down to the network you connect from.