Could it be the actual GIFs that you're using? Were they perhaps purchased somewhere?
No, I just went to this site and downloaded some random ones to my Desktop and started testing:
<http://www.gifanimations.com/>.
I sent these from one of my email accounts to another, both through Mail. Having the compose preferences set to Plain Text was a guarantee the images would not be animated, so I changed to Rich Text and selected a rich text signature for the account I was sending from. While the images don't animate in Mail when you create them, once you've sent them you should be able to go back to your Sent mailbox and open the message and see it animated as well. However, I believe the recipient's mail program will also need to be set to read HTML or Rich Text emails, or they won't get animation regardless of what you do.
You might also want to test the
Balzac email client, which does support HTML messaging.
Mulder