While some else may recommend a small utility or simple file edit to get the job done, I'd like to recommend Spyware Blaster. The free antispyware program contains a list of ActiveX controls, cookies, and websites which are known to contain spyware and unwanted goodies. Once the program is configured, it will automatically block these offenders, even if the program isn't running! (It won't tax your system resources.) It works with both Internet Explorer and Mozilla/Firefox. Aside from that, it can back up your Internet Explorer settings and allow you to revert back if something becomes screwed up.
By now you're probably wondering why I'm recommending this program as a solution. Well, if you go tools->Misc. IE Settings you'll find the ability to change the IE Title, in this case ''Microsoft Internet Explorer provided by Verizon Online'' to whatever you want. Since this small (2.44MB) program removes your particular annoyance and protects you from certain types of spyware without using precious system resources, it is definately a must-have.
Hope this helps,
John
Back in the day, I had Verizon Online DSL but have since switched to a Optimun Online. Every time I open IE, the browser title reads, "Microsoft Internet Explorer provided by Verizon Online". How Can I remove this permanantly? So far, deleting all the Verizon folders I can find hasn't worked. I'm running XP SP2, P3 700mhz, 256 RAM on wireless network. Thanks.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic