Yes, make sure you un-install cleanly through Programs and Features. This should get rid of any registry settings that might cause problems. Then, if anything of SH3 remains delete any folders belonging to SH3; which are the install folder and the one in (My) Documents. I suspect your previous patching attempts were done in the wrong order or something.
You mention you got it patched up to version 1.5. That does not make sense, as SH3 never got higher than 1.4b. You must be mistaken with SH4 I think.
You also tried to apply patch EMEA 1.0 to 1.3. But wasn't possible because a file was wrong. First of all, there should be an all-inclusive patch all the way to 1.4b for EMEA here (as you are from the UK):
http://www.silenthunteriii.com/uk/updates.php
First install Silent Hunter 3 cleanly, I suggest a folder named c:\games\SilentHunter3.
Don't run the game yet, but apply the patch to 1.4b first.
Now do a test run of the game.
If the above went well, consider applying mods, like GWX.