Attaching items to contacts

[faddat]

We have had a bit of trouble attaching items to contacts in our office,
and are unsure why. We use a public contacts folder to serve as a
directory of our company's clients, and with the majority of those
contacts, it is possible to attach items-- tasks, e-mails, et cetera,
to a contact and get a nice little envelope icon in the notes field.

For the minority of these contacts, however, the attach feature simply
doesn't work. Has anyone heard of this happening before, or can anyone
speculate on how to remedy this?

Thanks!
-Jake