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.
I'm very interesed in solution to this particular problem. Please keep us posted about progress.