After a lot of tries and retries I finally got an iPhone with the latest 1.1.1 firmware to unlock for any carrier.
I followed the steps on THIS page.
After you’re done with this you still have to put Installer.app on the phone, BSD Subsystem and OpenSSH again on the phone.
Finally you put anySIM.app into the phone.
Tricky but doable.