If your solution doesn't absolutely, positively have to be in Perl, then maybe a call to HTML Tidy would be the appropriate solution. It takes broken input and does its best to send it back to you as clean HTML. I use it in a lot of my projects.

Another solution I use is to not allow HTML formatting in user input, but maybe you don't want to force your users into learning one of the various HTML shorthand languages. Still, using Text::Textile to generate HTML from user input might be a little easier than making sure your users are always creating correct markup on their own.