If you want scalable graphics, you should look at SVG. I don't know offhand whether Mobipocket supports SVG, but epub certainly does. Several programs are available to create and edit SVG. Two Open Source ones are Sodipodi and InkScape.
If the maps in the PDF are vector-based, you should be able to convert these to SVG without too much effort.
To convert a bitmapped image to SVG, you can either hand-trace the image or try one of the various programs that attempt to do this for you. I recently came across this web site
http://vectormagic.stanford.edu/. The results look very impressive, although I haven't tried it yet. You can always edit the resulting SVG in one of the other programs I mentioned above.