most commonly, folks have Outlook Express set to the default security setting of 'block access to potentially dangerous attachments'. the user will often report, 'no attachments' but if they read screen carefully, they will see yellow bar with warning that outlook express has blocked attachement. if this is the case, fix with Outlook Express/Tools/Options/security clear check box pertaining to attachments
that was good, trying to email it to yourself.
lots of reasons for this to happen. did it used to work? what changed? sometimes your end will strip it out if too big or looks dangerous. ditto for other end. so thing is to find out what will work. you already tried 'intra-network' test that worked. you need to try to get it to work to somebody with internet account. somebody else besides this particular user. have you mailed attachments to this user in the past? is it possible the user is using outlook express or some other mail client with security setting prohibiting see attachments. this is why you need to prove it will work to somebody else. then you can get user to investigate.
how about if you email it to a hotmail account. can you make yourself a test hotmail account and see if it goes thru.
sorry if you've already tried all this but i would try another trick. rename the attachment so that it doesn't look like any file windows knows about. i mean, if it is called myfile.doc rename it myfile.dox. if it is called myfile.zip, rename it myfile.zix. see if that will go thru. of course, the user will have to detach it and rename it to work