The mobile internet on my new phone seems much faster and more usable than it did on my old phone. The main thing that helps is that the phone goes straight to a google search page whereas on my old phone I had to wade through a load of vodafone branding. I am finding it handy to be able to google whereever I happen to be rather than have to remember to do it later.
I think the last time I used the internet on my old mobile was when I had sold my car and needed a taxi home from the wilds of Thurrock, alien territory. I went through the vodafone crap and found a search page and searched for local taxis. I got about three references, one didn't answer, another was limosine hire and the third was a bus company. I walked for miles that day.
I think (the phone doesn't make it obvious) I am using plain old WAP for browsing. I don't think any gprs is set up and I've turned off the 3G search as I have read that trying (and continually failing) to scan for a 3G network is a waste of battery power. The performance on plain old WAP is ok.
At work one of my chores is to set up the email on the managers new smartphones. That job has put me off the hassle of having one of those and the speed that the email downloads at isn't wonderful. I have installed the gmail reader on my mobile and that was much easier than trying to set up imap on a nokia. Oh, if only the company used google apps...
Peter's Moblog
The K800i is a solid device, next time you need local results you should use the new Google Maps which can triangulate your location using just cell towers, just google "google maps mobile"
and since you have a K800i, which lets be honest, has a poor browser, i recommend you install opere mini as well.