First error message I got:
"The feature you are trying to use is on a network resource that is unavailable.
Clik OK to try again, or enter an alternate path to a folder containing the installation package 'QuarkXPress 6.0.msi' in the box below"

I didn't remember where I've put the CD with the original installation package so clicking Cancel I realized that it's not going to be that easy to remove the program, as the second error message popped-in: "The installation source for this product is not available. Verify that the source exists and that you can access it."

Ok. I've decided to delete the installation folder completely, but I didn't want to leave the registry entries not cleaned. So after a little research I've found a utility called WINDOWS INSTALLER CLEANUP that helps safely remove Windows Installer-related registry settings from your computer for certain programs that don't want to uninstall. You can download it (and read more about how it works) from here: Description of the Windows Installer CleanUp Utility.
Once downloaded simply install it following the wizard

Now to cleanup Quark installation (in this case, but this happens with Office too) go to click Start, point to Programs, and then click Windows Install CleanUp. You'll see the interface of this utility and from that list select the application that you want to cleanup (Quark in this case) and after that click on Remove.

On the next window you'll get a warning, just click Ok to complete this process: "Warning - All items selected will be removed from the Windows Installer database. In order for the items to work properly, you must individually re-install all items selected. Select OK to continue removing product, Cancel to abort."

Last thing to do is to click Exit to close the utility. Now the registry keys for Quark and the entry in the Add/Remove Programs aren't there anymore and you can remove the rest of the Quark files. As I mentioned above this might happen with Office too, as stated in this support kbase note: "Error 1612. The installation source for this product is not available" error message when you install or remove Office XP Service Pack 1