SBS 2003 User mailbox limit exceeded, after increasing size can not receive external emails but can send

The error has shown nothing related to mailbox size? Try sending him one internally, if it is the size limit that restricts him on receiving it will happen to internal email too (and you should get message saying the recepient's mailbox is full - or something like that).

Internal emails can be sent and received; no error messages.

Maybe the point value is too low on this one! OK fine lets make it worth...
500 Points! Oooooooh...

One thing to be sure is that the error has nothing to do with mailbox size, otherwise the offending user will not be able to receive both internal & external emails.

Error 5.7.1 is related to permission issue. I quoted this from a Microsoft article "The recipient has mailbox delivery restrictions enabled. For example, the recipient's mailbox delivery restriction is configured to only receive mail from a specified list. Other mail is rejected."

I am not saying thats the cause of the problem but its worth checking it out. Here is the KB article in full :
http://support.microsoft.com/kb/895853