If the error is accurate, you can try telling Wine about your VRAM directly, instead of making it figure it out. Use Programs > Run Command. Select the bottle with ST:O in it. Give the command "regedit".
In the registry editor, navigate to HKEY_CURRENT_USER/Software/Wine/Direct3D. If there is no Direct3D key, use Edit > New > Key to create it. With the Direct3D key selected, do Edit > New > String Value. Name the new value VideoMemorySize. Set its value to the number of megabytes of VRAM you have. For example, "512" (without the quotes).
When I run ST:O, it complains about my video card (GeForce 8800) and offers to run with lowered settings. Does it do that to you? If so, the obvious thing to try would be to accept the lowered settings.
If it doesn't offer that option, there may be a way to force it. I don't know off-hand if the game keeps its video settings in a config file, the registry, or the like. Or if it accepts command-line parameters when launched. You might search the web to see if that sort of thing is documented somewhere.