That's truth, convert the entrie site to CSS is real nightmare, but it is possible.
I have converted(80% and still working on it) x-cart skin to css and valid XHTML 1.0 Transitional, take a look(ignore design):
http://www.7danahost.com/xcart
Also, I have converted the default orange skin to valid XHTML 1.0 Transitional (not table free), I can share this skin if someone is interested, just drop me an e-mail at info @ 7dana.com.