Thanks for the help, Ryan!
But I got an AVS mismatch error again

. No idea what that is all about. I even looked up my working paypal account because of the hyphens in my address, but that`s not it. The only thing I could come up with now is the state/province entry, as I never filled that out anywhere else, I think... But as it IS the province I live in, that would mean there is a db error somewhere in the validation process. Seems unlikely to me, though. No further ideas now, maybe I just try again tomorrow.
All the best, Alex
EDIT:
It seems I’m not getting anywhere. The error message reads: "The transaction resulted in an AVS mismatch. The address provided does not match billing address of cardholder. (Response Reason Code: 27)"
But that IS my address in correct spelling, and although I haven’t used this card for very long, I don’t have problems paying a US and a Japanese hoster with it through paypal.

Do I have to insert the country code letter in front of my postal number? I didn’t try that one. Or do you have possibly have any ideas on whom I should contact about this issue?
Greets, Alex