Well that is stupid, my card is working everywhere just fine. So I called my bank to see what they can say on the issue. My bank called Visa and asked them. Visa told them, that they have blacklisted the "dealer" or payment service company for security reasons because of unusal activity and that I will not be able to pay to that dealer.
I wrote that back to Nokia, let's see what they are saying. Quite funny that Nokia is not aware of the fact that at least millions of german visa cards (from my bank) are blocked for at least a week now. Nokia should fire all those employers in charge of the ovi store. They are failing at so many levels.