I tend to run a lot of my stuff through HTML-Tidy which is great for fixing/cleaning up HTML code.

You'll find that most non-compliance warnings can be ignored, most browsers don't comply with the W3C standard anyway. Now that style sheets are (more or less) standard, though several versions of Netscape are rather broke, I rely on this and use as simple html as possible.

Regarding CGI.pm to generate your HTML, I really wouldn't bother, I hate having the HTML in my scripts, it makes maintance a pain and it stops a non-programmer being able to easily change things. Personally I like using HTML::Template as it seems to work well. I find the designers I work with can deal with it without any problems.