Hello - I can't answer all your questions, but here goes...
I just upgraded the T420 in my sig to Ubuntu 12.04 - everything worked right out of the box. Given the specifications from here: http://support.lenovo.com/en_VN/downloads/detail.page?DocID=PD015796
, I'd say you'd be in good shape with compatibility (you did say it was certified for Ubuntu). I'd recommend getting an Intel Wireless card specifically as it's performance is better with fewer potential problems in Ubuntu than the Realtek card (which is the Thinkpad AGN model).
Regarding purchase with Linux, Lenovo doesn't offer that option. They will sell a machine with no OS (or PC-DOS) to a corporation, but not an individual. From time to time, those machines will show up on the Lenovo outlet.
They also won't give you a discount on the OS - at least in the US. Since you are in the UK and part of the EU, you may have some better luck getting a refund via EU consumer protections. Here is a thread with some interesting information: http://forums.fedoraforum.org/showthread.php?t=139627&pp=15
. It looks like it's a hassle and you have to take pictures of yourself kicking "no" on the EULA, etc.
I'd check again on the Ultrabay as I do not think that the E series machines have ultrabay capability...
Good luck with your machine and way to go on running Ubuntu