So, why use CGI.pm for generating HTML? For small test examples, especially for this site.

Is there any real gain in using CGI.pm for generating HTML? Yes. These methods come to mind: header(), param(), query(), upload(), cookie(), and start_html(). [oops, only two of those actually generate HTML, 3 if you include cookie ... i changed my message mid sentance :/ ] The rest are supplemental, IMHO (and i may have missed a few more 'important' ones).

• "A really complex data structure -- just for a form laid out in a table..." If you are saying what i think you are saying, this is where a templating solution shines - your form is just HTML with a few special tags. However, if you are not comfortable with complex data structure, you are going to be hurting when you start using templating solutions. Nesting loops can be tricky, but never fear ... you can always ask us for help when that time comes.
• "I've got ugly-ass code -- even with CGI::Pretty..." Sounds like you are not using the most recent version of CGI.pm (2.93). Older versions of CGI did output HTML tags in all uppercase, but newer versions use all lower case tags. You can specify which HTML standard you want when you use CGI:

  use CGI(:html2);
  [download]

  Other function sets are html3 and html4. There are more ... you'll have to experiment to see what they do. ;)
• "I've got code about the same length as the HTML would have been if I'd written it myself." It's probably more code. The benefit of using CGI.pm to generate HTML is not to reduce code, but instead to hopefully have more readable code - that is, you shouldn't have to strain your eyes too hard trying to decipher what is Perl and what is HTML. But, the real winners here are templating solutions.
• "I've got the stickiness I wanted ... I've got stickiness I didn't want." Yep. Welcome to CGI Form User Error Handling 101. There is no real easy way to do this, because everybody has different needs. I haven't tried HTML::FillInForm yet, but i'll bet it's nice and worth the time you spend to learn how to use it.
• "CGI.pm doesn't like me to print the start of my table, print the rows and print the end of my table..." Others have already addressed this point, but i wanted to stress that table and list generation in CGI.pm is about as hard as it gets. You have to master map first:

  print table(
     {border => 1},
     map Tr(
        th({align=>'right'},$_),td[param($_)]
     ), param()
  ),
  [download]

  That code will print whatever params were submitted. But ... if you think that's tough, know that when you use a templating solution, you have to massage a data structure into another data structure suitable for the template. Using CGI.pm or a templating tool does not alleviate the need for you to learn advanced Perl code.
• "I'm using CGI.pm so I don't have to write my own HTML any more." Nope, that's the wrong reason to use CGI.pm. CGI.pm only changes the method of writing that HTML - you will always have to write your own HTML, unless you have someone else to do it. And that's why templating solutions are such a boon - they allow you, the programmer, to concentrate on the code, while allowing another person, (most likely a non-coder, HTML designer) to write the HTML. Again, using CGI.pm to gerenerate HTML is better for small examples / testing.
• "What have I gained for my two hours?" Well, hopefully you learned something. Besides two hours is nothing, i've invested well over 20 hours in reading the CGI docs, fumbling with getting those darned maps just right, etc. Even though i use HTML::Template religiously, i still am glad that i invested that time. Remember, i actually like gererating HTML with CGI.pm -- it can be fun if you are twisted enough. ;)
• "Do I just need another coffee?" If you aren't jittery enough yet, then yes ... grab another cup. ;)

UPDATE: (Tue Jun 17 2003)
Here is an example of using CGI.pm to generate HTML that makes sense, but it is an isolated example: (jeffa) Re: automagic-HTML regex

jeffa

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)