When trying to start my eJukebox it says:

"Database Corruption Detected. eJukebox will now attempt to repair its Database"

and immediately after that:

"Database Could not be Repaired. Download and install the latest upgrade.. etc"

I've tried that several times but it doesn't help.

I guess I should uninstall eJukebox completely and start from the scratch. But how to do that - I can't find an unistall option in the software? Of course, I could just delete all files, but are there some registry keys that should also be deleted? And what about my registration key, will it still be valid after complete reinstall?

Follow these instructions and everything should be fine.
http://www.audiosoft.net/forums/viewthread.php?tid=332

Downloading that 184 kb asn-file did the trick, I can once more start eJukebox succesfully.

Strange that simply deleting the old corrupted file didn't help.

I also noticed there is an uninstall.exe in eJukebox directory, but why isn't it listed in Windows' Program menu nor in Control Panel (add/remove programs)?

Yes i agree... I always keep a spare .asn file available, but that's because i know of the situation. eJukebox should be able to create this empty .asn (well... since it's almost 200kb it cannot be entirely empty :p) by itself, if you have deleted or corrupted your .asn file.