"This email address is not valid for use as an Apple ID" Apple belatedly decided they don't like something about my email address, but won't tell me what.

I just bought a new Mac for work and my employer paid for it so I set up a new Apple ID with my work email address rather than use my own. It seems you can't buy anything from Apple without using an Apple ID. That all went fine as far as can tell, Mac arrived, I switched it on and all works as expected but is a bit insistent about requiring my Apple ID for various things. 

So I need to verify my Apple ID; they send an email with a code number; I type in code number…
"This email address is not valid for use as an Apple ID"

No explanation, and no instruction what to do about this. I'm stumped.

Anywhere I try to access my Apple account I am told I can't get in until I've verified my ID, but can't because my email address is somehow not valid.

I have checked that I don't have the work email address associated with my personal Apple ID, so that's not confusing anything.
If you use work e-mail and you just got the new e-mail account from work, it probably uses a work domain.

It extracts the MX records from the email address and connect to mail server (over SMTP and also simulates sending a message) to make sure the mailbox really exist for that user/address. Some mail servers do not co-operate in the process or have a delay, in such cases, the result of this email verification tool may not be as accurate as expected.

This technic of E-mail validation through the sending of an E-mail interrupted before the end is a technic used by criminals to perform stealth E-mail verification. This is the reason most serious companies will block these interrupted SMTP handshake. This is a bad method to check an E-mail.

Often with not recognized or newly registered domains Apple takes a few days and then it will magically accepts the e-mail.

You can see here https://verifalia.com/validate-email what a e-mail validator will check. And the results.

If it doesn't work after serveral days, you should contact Apple Support.