I don't do anything at all in the registry. If you delete the contents of the DATA folder, it will rescan everything from scratch.
Is it possible you're scanning directories twice? WinCab has an internal setting of SongPath=. to include the jukebox directory and anything below it. So if you have a SongPath1=c:\Jukebox and that's where the jukebox is installed, and all your music is in directories under C:\Jukebox, all of your songs will be scanned twice. They still shouldn't show up twice, though.
Please delete the contents of the Data directory, go into jukebox.ini and set DebugLevel to 5, run the jukebox, and if you still get double songs, send me the resulting jbdebug.log. Actually, if your executable is still called jukewin, you're using an older version and the log file will be called allegro.log instead. Or you're still using 2.41, in which case there won't be a log file at all...
--Chris