Good breakdown. One addition for the reply in step 3: before offering the credit-note route, ask them two things in the same email so you don't go round twice: (1) the exact legal entity name and billing address as it appears on their VAT registration, and (2) whether their finance team needs the VAT number on that specific invoice to reclaim VAT, or only on future ones. Then check the number in VIES yourself before you issue anything, because a typo on a reissued invoice means a third document.
Also worth keeping a saved reply with this checklist: customer record updated, tax ID type correct, VIES result noted, old invoice decision (keep vs credit note plus reissue), and who on your side confirmed the approach with the bookkeeper.