Awhile ago games that used 8bit colour tended to perform poorly in Wine when rendering on a 16 or 24bit display. This didn't affect all games, games that didn't need to redraw much of the screen performed alright.
The second, and I can't find any links for this at the moment, was using AIGLX / Compositing to do the depth translation / palette mapping within X
I stopped following these developments a few years ago. However, I now find myself with a new netbook (Ideapad S10e) wondering where these developments went. I've been unable to find anything on this newer than 2007.
Interesting. It's related, but a separate approach to addressing the same issue (as well as a few other issues). The DirectDraw / OpenGL stuff that Stefan Dosinger was working on tried to bypass need to create a proper DIB engine.
The patch-sets against that bug may prove handy in trying to get a few games working though, thanks for the link.
I'll see if I can find something on the Xorg / Composite line of development.