I already tried reinstalling gpg4win without first uninstalling it (I thought it might repair corrupt files) but now I uninstalled first and it is working again.

I searched through C: and D: and found it in D:\Programme\GnuPG\bin and in D:\Programme\Gpg4win\bin - both seem to be created by gpg4win. I'll try reinstalling, hopefully without deleting my private keys...