I am assuming that the problem only occurs when you send emails over the Internet?
Have you tried recreating your signature?
Also, the way I created Autosignature was to create a new email, type in my Autosignature and mess around with the formatting, then select Autosignautre under the Tools option. I sent VERY long autosignatures to myself over the internet (to another address) and they came through OK.
Also, check your normal.dot as you may need to recreate that if its gotten itself confused (poor little thing).
Finally, this is what I got from Microsoft, although this may be teaching you how to suck eggs, in which case ignore it!
"How to Create an AutoSignature When You Are Using Word As Your E-mail Editor"
1. Open a new e-mail message.
2. On the Tools menu, click Options.
3. On the General tab, click E-mail Options.
4. Type a name for your new signature.
5. Under Create Your E-Mail Signature, type and format your e-mail signature.
6. Click OK twice.
NOTE: By default the AutoSignature is applied to forwards and replies, and to new e-mail messages.