You'll probably need to wait for Stefan or Henri to respond to figure out what to do. Though, it appears DDraw can be patched to do a second enumeration loop with WINED3DFORMAT_P8 if the first was with WINED3DFMT_UNKNOWN.. whether or not this is acceptable, I'm not sure, but it's an idea I just had.
You can change WineD3D to allow WINED3DFMT_P8, but you have to modify d3d8 and d3d9 to filter it out. This is the correct approach then. Injecting P8 in ddraw will work too, but it is not correct from the design point of view(since then wined3d says "I can't do that", and ddraw says "But I insist you can do it"