How can I decrease and optimize the size of my animated wallpaper?

[MobileVisuals]

The problem I have is that my customer MediaPlazza requires that most of the animated wallpapers should be less than 15 kb. It seems impossible to make them that small and still look good. I am using JASC animation shop and even if I only use 5 frames and optimize it as much as I can with the optimization wizard, the wallpapers become too large. My original pictures are JPEG-pictures of lotuses. Here are examples of my original pictures:

http://www.astralvisuals.com/Lotuses.htm

How can I make the wallpapers smaller?

[petrib]

Use less colours, simpler images (with bigger, uniform surfaces). The more complex an image is, the bigger it is in GIF format.

Maybe it is also time for MediaPlaza to lift their limit of 15KB (I'm sure most phones - probably all - can handle much larger images/files than that)? Have you asked them? The decision may have been made a long time ago and nobody remembers any longer why, or the reasons are no longer valid today.