Except for very basic (probably one-shot) scripts, I always use templates for HTML. I usually use HTML::Template, which has low overhead (more in the sense of programming time than computer time), and is very simple to use. I can't think of too many cases where I wouldn't want to use HTML::Template (or another templating system).
The main reason is getting the HTML as far away from your code as possible. Once you do this, a lot of problems just don't exist anymore.
While sometimes templating systems can give you a performance hit (not that this is usually too important - network speed is far more of an issue for the vast majority of users hitting your scripts) they often make it easier to tune performance if you need to.