Theming

i think you have to

a) Add a themename_preprocess_views_exposed_form(&$vars) in your theme.
b) Add a template suggestion, see http://drupal.org/node/223440 for your view.

Therefore you have to user $vars['form'] and search for the view variable.

Then you can use a template per exposed form.

This might be better with vesrion 6--3 of views or by a patch already somewhere in the issue queue.

Keith Hurst
Based on this post http://drupal.org/node/837112#comment-3140726, I think you found the solution
Please reopen the post if I'm mistaken