553 Requested action not taken: mailbox name not allowed or chunk too large

I am reconfiguring a network. We are using MS Exchange 2003 on a 2000
server. I have POP3 and SMTP services running but when remote users
who connect via POP3 try to send any email to an outside email
address they get:

553 Requested action not taken: mailbox name not allowed or chunk too
large

They can send mail to internal users i.e. other users in the global
address list.

It's a few different users so I ruled out the Apostrophes issue
mentioned in:

http://www.faqs.org/qa/rfcc-193.html

The company has a WatchGuard firewall and won't trade up anytime soon
so that may be the problem I just need a little advice on what
settings need to be changed.

POP3 is enable for incoming and outgoing. SMTP is enabled for
incoming and outgoing. Both are NATed to the Exchange box.

Anybody else run into this and have any sort of solution?

thanks