My impressions was that the corporate license was per user.

But when I try to register the license with the same user, using the offline license-key from the first set-up, I get an error message stating

Verification Failed
Unable to verify your registration details. Would you like...

The computer names are different and the license key checks out ok.
Is the license perhaps hard coded to the email address I used during the purchase?
I was aiming at using a different name internally (still in the same domain).

No.  Corporate licenses are tied to an email domain.  However, a separate email address would classify as another user.  You must use the target users own email address on the domain when registering.

So you used a different email address with a different machine name and you got back the same registration key?  Are you using manual registration?