How to theme a select box with multiple selection enabled
The Improved Multi Select widget sounds right up your street:

The Improved Multi Select module replace the default multi-select boxes with two pannel list and search.
The first panel holds the options that are available, and the second panel holds the options that have been selected.

It looks pretty good too: