Wow. I'm so happy: My ISPs Support Hotline helped me with the Speedtouch 585 (I bought it there) and it now works (almost) without any problems:
The simple trick was that I had MAC address filtering on and set the Speedtouch to allow only the Nokia 770. For some reason (and I guess I better start a separate thread about this) this doesn't seem to work. I have to set MAC-filtering to "off"; well, I can live with that for the time being. After all, I had no WLAN-connection at all so far.

After my disappointing experiences with 2 DLink-Routers I was so obsessed with the idea that it's a WPA-problem, that I never thought of really checking and re-checking all the other parameters.

Thank you all for your feedback about working routers, I'm sure it will be of value for other visitors here.