Sure, but there's only one way to completely uninstall IE and it sounds like that's exactly what they're doing.

This isn't true. Off the top of my head, Google could replace the executables (incl. DLLs) with ones that do nothing but throw up a "disabled" sign. (Which would also take care of OLE/ActiveX embedding of IE in other apps.) I see below that there are better ways of doing this from more Windows savvy folks.

I'd have assumed that Google Chrome or Firefox would have been default browsers at Google considering their involvement.

also, the infected URL was sent through MSN Messenger and upon being clicked, it launched the infected page. That would mean, correct me if I'm wrong, that the default browser was still IE.

Also, are IT policies applied consistently throughout the world or different regions have a diff. IT policy?

Much easier. They could for example setup Active Directory policies to disable the use of IE by default.