If you can get Be you can probably get O2.
I say probably because in the beginning was Be. A bit niche-market for the techies. Be set up a pretty good ADSL2+ network. (That means up to 24Mbps - BT are just about getting round to a modified and less good version of it 3 or 4 years later).
O2 decided that like Orange they needed to be in the internet market. Rather than start from scratch they bought Be. So O2 runs on (in general) the same equipment as Be, certainly at the exchange, but they seem to split the number of connections they each have at an enabled exchange when it is enabled or upgraded. So one may have free connections but not the other.
Back to the subject. O2 includes email, and is generally better value for money especially if you have an O2 mobile. See the MKD document. However it isn't as flexible or easy to get some settings changed if you want a bit of control. Think O2 = mass market, Be = internet sophisticates. (Commonly known as geeks

).
However I am completely and utterly "anti" ISP-hosted email services. They are on balance a pain in the ... (think of an alternative next word to "neck").
In particular because of the hassle, which grows each time, of telling all your contacts, changing all your partner's or your internet shopping accounts, updateing information email sources ... every time you migrate.
It locks you in, is often unreliable, and usually gives you a completely yukky email address.
Purple Cloud I have been with for 2 years now - just renewed my main domain registration through them. Not the cheapest but since then I have added four more domains and two web hosting packages. So I must be happy - and I'm easily upset by poor service or supplier performance!
£7.50 gets you a .co.uk or .me.uk domain, (more choice on .me.uk as far fewer registrations using it),
yourdomain.co.uk registered for two years with Nominet, the UK authority, in your name not Purple Cloud's. Some other providers tie you in by registering it in their name and charging you to release it if you want to move to a different provider.
Then £10 per year for an email package to go with it.
something@yourdomain.me.uk. Ten mailboxes, unlimited aliases, normal POP3/SMTP plus IMAP and webmail, and Spam Assassin running on the servers. Or £20 for a basic web space account which includes that email package. www.
yourdomain.me.uk.
It's dead simple to sign up and be up and running normally within a few hours. My additional domains and web space took minutes. The only slightly complicated bit is turning on Spam Assassin, I think it is off by default, and the user control interface is far from good. (Plesk). They tell me a more user-friendly one is to be introduced some time in the future.
So you get a good-looking email address that you chose, notify all your contacts etc. as above straight away, and start sending and receiving from it immediately while still reading from your current one to see if any turn up that you have missed.
Then when migration day arrives absolutely no panic about getting your email service with the new ISP set up and trying/failing to notify every contact. Normally nothing at all to change! (And if you see any port 25 blocks mentioned anywhere, then with Purple Cloud you will have one change, perhaps a few more depending on how you set it up, to make in your mailbox set-ups in your email program).
You might find
this post interesting, particularly the bit about the mobile.