You're so right - it's really quite horrendous. I've used two solutions for this in the past (neither Perl though, sorry) :
Microsoft themselves have released a utility to do this - presumably available from their website
Macromedia Dreamweaver has a specific function to do this
The second of these obviously can't be incorporated in a script, the first probably can't, but perhaps you could persuade your users to run their html files through the Microsoft utility, on their Windows desktop?