I used to have a 8900 curve. It doesn’t have a search bar like the new ones, and from Krytons reply above it looks like the menu options are different 😕 (now have a 9300) I don’t remember a ‘set up new email’ option, but could have missed it too.
I added a gmail account to the old 8900 by going on line at mobileemail.vodafone.net which take you into your account (probably not if you are an o2 user though). I had to get the guy at work who set the phones up for work use to give me my username and password (your phone will already be registered with your work address i assume) then you just login in and add any additional addresses. If you don’t fancy asking work try calling the network provider for info??
Sorry not much help…