Attachments not visible in Outlook 2002

This is actually happening in Outlook 2000 as well as 2002 — when a message comes in with an attachment, it is not visible. This is not consistent with every message, and yes, the attachment column is on. When I actually open the message (rather than just preview), I can select “Save Attachment” from the File menu, save it and then open it up. The CEO, however, doesn’t like this solution – he needs to be able to see the attachment in the message and click it right there to open.
I have gone thru Technet, all kinds of support pages, everything, to no end. Any ideas on how to just make the damn things visible? Need help!!!!