Ogg/Theora Video would be perfect to implement with Game Editor.  As far as I understand the license is free.  It has been used in the GledPlay project which has since died. 
GledPlay: http://www.pocketmatrix.com/forums/viewforum.php?f=61
I apologize if we are not allowed to post links.
I see that it has been mentioned that we can use animated gifs.  Since I haven't bought Game Editor yet, is it possible to play the animated gifs on a Pocket PC?
			
		