This can be done easily with Overlay/Chromakey transition.
The overlay transition is discussed thoroughly on Moviemakers.Net forums.
here is the direct link to the thread.
http://www.windowsmoviemakers.net/Forums/ShowPost.aspx?PostID=3397
You dont need a transparency in the gif actually; a gif with any constant
color background would do. A normal movie would also work instead of
animated gif. The only restrictionis that the color value needs to be
exactly the same all over the background. This is very tricky as due to anti
aliasing and dithering the color value changes slightly near the object
boundaries to spoil the effect.
Note the rgb value of the background color and make the custom
overlay/chromakey transition using that. Best if you use black as the
background color.