If your scripts aren't long-lived (ie. servers, mod_perl handlers), then it's unlikely that you will notice or care about memory leaks. If, however, you are writing code that is expected to stay resident for days, weeks, or months, then certainly memory leaks are a serious issue, as is the related problem of making sure your data structures do not grow unchecked.
AFAIK, the only thing that can cause a memory leak under Perl, outside of badly written XS code, is a circular self-reference, although I'd bet that there are some pathological memory allocation patterns which fragment memory to the point of appearing to cause memory leaks.
The HTML::TreeBuilder example is not really a case of a "module causing problems", since it includes a method for cleaning up after itself. I also wouldn't expect DBI to be a source of any memory leaks, since it's such a well-tested and often-used module. Regarding your last question, wrapping calls inside an eval would do nothing to prevent a memory leak.
s aamecha.s a..a\u$&owag.print