For reference since the O2 customer care is unhelpful if you own a Windows Mobile device (not purchased on contract from O2) and need to use the internet:

Go to [Start]
Tap [Settings]
Tap [Connections]
Tap [Connections]
Under [My ISP] tap [Manage Existing Connections]
Tap [Edit]. If this is not present tap [Add a new modem connection]
The [Select a Modem] drop-down box should be set to:
XDA Exec: [Cellular Line (GPRS, 3G)]
Tap [Next]
The [Access Point Name] should be set to: mobile.o2.co.uk
Tap [Next]
The [Username] shouldbe set to: o2web
The [Password] should be set to: password
Leave [Domain] blank
Tap [Advanced]
On the [TCP/IP] tab, only [Use Server-assigned IP Address] should be selected
Tap the [Servers] tab
Select [ Use Specific Server Addresses]
DNS: 193.113.200.200
Alt DNS: 193.113.200.201
Tap [ok]
Tap [Finish]