First of all, I had to add the Evolution EWS service which wasn't installed by default:
sudo apt install evolution-ews
Once that was installed, I was able to go through the account setup:
Edit > Preferences > Mail Accounts > Add
The auto discovery failed, but by manually setting the type to Evolution EWS I was able to get it working.
The magic URL that worked for me was:
https://mail.nhs.net/EWS/Exchange.asmx
Once that was set, I was able to get the OAB URL too by clicking on the Fetch URL button.
You have to be careful not to store your NHS Mail 2 password in the security otherwise it will eventually lock your account.
I'm not entirely sure that NTLM on EWS is a good authentication method to use with NHS Mail 2 so I will be following this up with Accenture when I'm back at work - Not sure what kind of reception I will get to that though.
Anyone have any thoughts of the merits of NTLM vs Kerberos authentication in an Internet facing application such as EWS?