I have made a couple of pretty satisfying maps using a vector map of the world (like, the Earth world). I found one somewhere that had each country as a separate shape so I opened it in Illustrator and just starting moving stuff around, overlapping and inverting. The only problem with this method is that some savvy observer may say, "Hey, this Pirate Kingdom is totally the south coast of France!"

cheers,
Meshon