I finally received the replacement card today from customs. They didn't open the package for inspection so everything came here in pristine condition with all seals intact.
I have initially been told by the UPS that the declared price for the package was 650 EUR. It turned out it was actually 650 USD, so the duties + tax I had to pay was 137.80 USD.
The original card itself cost me 900 USD so with 100 USD shipping to Germany and 137.80 duties + tax now the total is 1,137.80 USD.
Now for the good news, the card is working very well.
My idle temperatures are good:
And so is load (although this is small load just for testing):
Thanks to everyone for help, and thanks EVGA for solving the problem for me. Now I am curious what the issue was with the original card.