Form-based CSS generation is fine as long as all inputs are strictly sanitized or validated against hard-coded lists.

As you guessed in #1, there is only one real copy of each theme file on each server, so the CSS would have to be stored in the db in the options table.

There is no amount of customisability that's too much. As long as we can look at the theme's code and be sure it's safe to use, it has a chance.

So, my question(s)
1) Why can't the css of themes be editied? Is it because each user does not have a "local" copy of the theme for their blog?
2) If so, would it be possible for a theme to do something like store the css in the database, then allow the user to edit the css via a text box on the theme options page? I know regulus puts several settings there, but I'm not sure exactly how it works.
3) If storing the css in the database is possible, would wp.com even let people use the theme <i>because</i> it allows editing of the css? (Aka, it's too complicated for Joe User.)
4) What if 90% of the css file was avalable for editing by using dropdowns, text fields, etc. on the options page?
5) What if a few of the critical options like bg color, text color, header image URL, etc. were avalable on the options page?

I guess I'm basically asking, how much theme customisability is too much? What are the requirements for getting a really, really customisable theme accepted to wp.com?