My personal quest has ended today. I found a sweet little program called Inno Setup. By itself it's a bit crap, cause you need to script everything, but if you install ISTool aswell (a GUI for Inno Setup) then it all falls into place.
By the way: I do own Visual Studio 2003 Standard, but Using MSI wouldn't update new versions of software properly/wouldn't replace running files without restarting (!?!??!!WTF)/added multiple entries for the same thing in Add Remove Programs/etc. Basically the user had to go to Control Panel/Add Remove and actually remove the program before installing.
I won't go into how much ClickOnce deployment is the totally wrong choice for the software in question. I do love the idea of it though!
Compression is even better with Inno (using lzma/ultra).
peace