Alright, quick update from me which I hope helps even more than the logfile (which I can post later, if still needed).
I just found out about this tool:
http://htcfanboys.com/download/xavierjohn22/?action=browse&folder=3130, which enables you to change some settings which are normally hidden.
I toyed with it a little and found a setting to set the prefered network type (Testing Settings -> Phone Information), which was set to WCDMA by default. I set this to "GSM Auto (PRL)" and it seems to be working fine now.
As far as I know, CDMA is US only.
At least, I disabled WiFi after waking up today, so the phone was connected the whole night. It switched instantly to my mobile data connection
.
Hope this info helps the developers. Don't know why with a GSM Desire it would be set to WCDMA
prefered.
At least, this setting should not be hidden.