...on the "paperclip" a window opens asking you to select the file to attach. At the bottom of that new window is a radio button that makes all attachments "Windows Compatible".
Give it a shot!, if it doesn't solve all, we'll try something else.
A few times I have had the problem that when I send an email attachment (using Mail 2.02) on OSX Tiger, that pc users receive the attachment embedded with the text of the email. They can't download the attachment separately, from their mail program. They ask me to send it as a separate attachment but I know no other way to attach it! I simply use the "Attach" icon at the top and select the file.
There is also one company that cannot receive my attachments at all, though when I send it from a different mac they can. The majority of people receive them ok, but it can be very frustrating with the odd client.
Any advice would be appreciated.