> I'm pretty sure the idea of managing to separate program logic and presentation for something that needs to output HTML is largely a myth. I've tried, again and again, to do this, but no matter what, you end up with HTML in your program code or program code in the HTML (even if the program code is some templating language, it's still code).

That doesn't mean you shouldn't make an honest attempt.
I like the way Wordpress or Ruby on Rails apps do it:
The first uses PHP files as the templating language. You use well-documented functions to fetch data, so the templates are really flexible, yet free enough from business logic, especially since plugins are quite easy to write.

In Ruby on Rails, the views are .rhtml templates which work a lot like PHP, which look like this:

<% @things.each |thing| %>
  <div class="thing">
    <%= link_to thing.name, :action = 'show', :id = thing %>
  </div>
<% end %>

But you'll still often code methods that spit out some HTML snippets outside of the views.

If you want to suceed at web applications, you certainly need a lot of discipline and to never allow a prototype to grow into a module without some serious clean-up, but you shouldn't follow the MVC approach all the way: the end users don't want to interact with applications, but with websites, and most web apps (especially PHP ones) feel way too stiff because coders are too disciplined to know when to blur the line between code and data.
The key to keep the website agile and the app seamless is to know the rules, to apply them religiously, and to break them all the time. That's really hard.
Well, sorry for going way off-topic.