I heard some good stories about
crossover office. It runs internet explorer on linux. Apparently, it might be possible to run Win32::IE::Mechanize on it. Haven't tried it, though.
Another way to go about it, is to install windows and the tests on a virtual PC like vmware, and run the webapp on the native linux system. VMWare works very well, as long as you have enough memory (I'd recommend at least 1 Gb for a linux system with windows XP under vmware).
Yet another way, is to port Win32::IE::Mechanize to mozilla, and I would be grateful for the person(s) to accomplish the task, but AFAIK mozilla is not as easy to script as Explorer, so it's probably going to take a lot of time.