I SOLVED IT!
Thank you all for the comments and for the various ideas on how to solve it. Based on your suggestions I solved this out for me - and here is how:
I had a AppleID in use under my Gmail-address, both as login name and as primary email address. And never got a confirmation for the Gmail-address. And I figured out that I already used the same email for another AppleID, whe I used the Gmail-Address as the primary one BUT a custom user name for login. It seems like the sign-up process with AppleID allows to register with a email address already used, as long as you have a custom user name tied to the other existing account. The inout it validated against the username only, not against the existence of the email address in the entire database.
So how did I solved this? I replaced the Gmail-address in my primary account to a spare email address - and got a confirmation instantly. Then I used the AppleID.apple.com to validate if I already have an account and found out that I have the one with the custom user name. I then also replaced the Gmail-address with a spare one and updated the account. Then I changed the email and the original account again - tata! - it worked, I got an instant confirmation. Seem like this process removed the non-working email completely from the DB. Now I can use my original login (and Gmail-address) for all Apple stuff.
THANKS!
Now, Apple - hire me for the Genius Bar!