Success!

After the phone call with VISA I contacted Nokia via the OVI-Support-form. They answered just a few hours later and told me to try to bye it again BUT NOT to save the credit card details for later use in the store. First this went wrong, so I called the service line given in the support mail. The first call was not successful, but they promised to call back later and after half an hour they did. No new advice, but told me, he wanted to give my OVI-Login to the shop support. This was at 13:00 MESZ (9 hours ago).

Now I was curious about it and tried it again and it worked!

So if the payment doesn't work for you, uncheck the "Save credit card details for further usage" (or whatever it called in your language) checkmark when typing your credit card data.

Now I try the game, download and install was fast (WLAN).
hobbsch