This is indeed seemingly impossible - unless you specifically define each cell's width and height, which kind of defeats the object of using a table.
Possbile solutions...
RGBA
Assuming you are going to use background colours you can always use background-color: rgba(200,200,200,0.5)
with a fallback to solid colours if it fails. Support for RGBA is in all of the top browsers, it doesn't work for IE8 and below however...
Transparent PNGs
The obvious easy one is to fallback to using transparent PNGs, but then this relies on the colours you are using being predefined and rather rigid.
Use -moz-element
Another mad solution to get FireFox to work (if you are using background images rather than colours) would be to use the background: moz-element()
ability. Here you create hidden elements on your page of each different opacity that you might require and reference them as a background via id. For example:
<div id="image1" style="background: url(image1.jpg); opacity: 0.5;"></div>
Then reference that on the element you want the background to appear on:
<td style="background: -moz-element(#image1);"></td>
I'm not vouching for this method however, it's rather inelegant and browser specific. Tbh I'm quite suprised to find that this problem is indeed not fixable (esp. in FF) using plain old absolute and relative tricks.
Don't us Tables
The more browser supported solution by far would be to drop using tables and recreate a table structure using good old divs and floats. The only problem with this solution is again you'd have to define most widths and heights and you wouldn't be able to achieve vertical cell alignments unless you fallback to something even more experimental like FlexBox.