I'm looking at Garmin's .gmap format, and so far I can't see any downside to distributing maps in this form (other than, maybe, people with really old computers and old versions of mapsource). Here's how to create and install a .gmap version of your own existing mapset.
First, create your mapset as usual and install with MapsetToolkit. Now create the Mac version of your map using Garmin Mapconverter - this is something you would need to do anyway.
Let's say your mapset name (the one displayed in Mapsource) is "test". Garmin Mapconverter will create a file named test.gmapi. However, you will see that is actually a folder under windows and not a "file". Open the test.gmapi folder and you will see a folder inside named "test.gmap". THIS IS ALL YOU NEED!
If you're doing this on the same machine, you'll need to use MapsetToolkit to UNINSTALL "test" before proceeding, since it has the same FID as the new gmap version. After doing this, simply copy the test.gmap folder to C:\Users\All Users\GARMIN\Maps
You have now installed the map "test" in Mapsource and Basecamp. No registry entries are involved. You can confirm by starting Mapsource. To completely remove this map, just delete the "test.gmap" folder from C:\Users\All Users\GARMIN\Maps and it will be gone.
So an installer script for "test" just needs to do a few things -
1. Check for the existence of C:\Users\All Users\GARMIN\Maps (see note below for possible issues)
2. Create this folder if it doesn't exist
3. Copy the test.gmap directory heirarchy to C:\Users\All Users\GARMIN\Maps
4. Provide an uninstaller to remove test.gmap
I believe that different versions of windows might store the maps in different places - I need to look into this. Under Vista, I can access the same folder at C:\ProgramData\GARMIN\Maps. If I use a command prompt and type "set", I see
ALLUSERSPROFILE=C:\ProgramData
I believe this can be used to determine the correct location on different Windows versions, but not sure how to incorporate that into an install script.
I'm not clear on whether there are permissions issues, etc that need to be addressed when installing as well. I'm really not a "windows guy" so I may need some help here.

What do you guys think?...