Greetings all,
Some good comments up to now. I do CGI based scripting almost exclusively and this is indeed a common issue for me and my team. However what we try to keep in mind is that a total seperation of logic from display is not always possible, especially with web-based applications. Our strategy is to utilize other technologies to help bridge the gap such as CSS or JavaScript. Standardizing styles can go a long way in terms of helping the programmers conform to the designers sense of style.
We usually define styles for HTML tags first, stuff like body, td, p, dir, blockquote, ...etc Then define custom styles (but standardized names!) for things like navigation links and any other funky stuff we need. This way if you forget the name of the custom style to use at least you will have a default style for most of your HTML tags and missings a style wont result in a non-conforming element.
It still boils down to you creating some HTML strings as you mentioned earlier, however you will now have a standard set of styles to work with. This way if your code ever needs a face lift you wont have to touch your code as much, just update the HTML templates and tweek the style sheet, so long as your style names stay the same you will be fine.
I know this is not the best of solutions but its better than hard-coding style related things in your scripts.

-injunjoel