I don't use HTML::Template or Template Toolkit, but I'm using a custom Template engine based on the (discontinued) HTMLTP, plus some custom modules for error checking etc. I beleive that the one I use is quite restrictive, but I find it impossible to NOT be able to completely seperate code from presentation.
I haven't written a single line of HTML on my code,since 2002 at least...

So, I beleive that with the correct analysis, and pre-design, you can always seperate the two.