I've written 2 pages illustrating how to create a nice looking menu by displaying images instead of the anchor text, using a stylesheet. There are no tables to structure the layout of the menu, instead the menu items are in an unordered list whose display is manipulated by the stylesheet. The example pages use XHTML 1.0 coupled with CSS level 1 (except for the hover pseudo-class) and should validate as such.
The examples are listed below. Note that the anchors default to a white background. This means that when you hover your mouse
over a link you'll briefly see a white background before the image associated with the hover pseudo-class is loaded.
You can avoid this by setting the default background of the anchors to transparent and setting the background of the list
to look the same as the hover images.
This is what the mindspill.net v3 grid-shade theme does (update: no longer available).
I've also prevented display of the h1 element. This is simply because the menu was
designed with the grid-shade theme in mind, which requires the header to be hidden.
View the source code to see how the effects were achieved.