Right now, I'm maybe 80% of the opinion that this really did come from HMRC, despite being told by their helpline that it's a phish. So how should they have handled the need to update their software?
First and foremost, the PAYE Basic Tools should be handling this. When I start up the software, it should check the HMRC gov.uk domain to see if there's an update required, and it should notify me to do it. This could, with a suitable crypto system, be made really secure and proof agains MITM attacks. Email is probably the worst possible way to do this.
But since their software doesn't do this (didn't it occur to anyone that it would need updating each year?), and given that they decided to tell everyone by email, what were the big mistakes they made?
1. The email should have been sent from the HMRC domain, gov.uk. Not from some third party domain (govdelivery.com). And especially, not from some third party domain while pretending to be from gov.uk.
2. The opening greeting should have been "Dear Dr Solomon" and not "Hello employer". Because on their database, as well as my email address, they have my actual name, which a phisher tends not to have.
3. They shouldn't have given a link to download the software. They should have told me to go to the hmrc.gov.uk web site, and they shouldn't have given a link to it. And they very much shouldn't have given a link to a third party domain (govdelivery.com).
4. And they should, perhaps, not have done this by email at all. If they'd sent a paper-type letter, then that would have been much better; phishers don't do that.
5. And by the way, why is the British government paying an American company to distribute their stuff; I'm guessing that the American company isn't doing it for free. Aren't there any British companies that can send emails for you and host your software?