I was confronted with a windowed mode, too, but Zenger's patch worked perfectly for me.
I'll try to give you a step-by-step guideline, based on how I did it:
1. Download the patch (V3) using following link: http://www.mediafire.com/?4h1at8stfc9cfiv
2. Unpack all the contents into the Outcast-directory (e.g. C:\Games\Outcast)
3. Run the patch (APPLYMEGAPATCH.exe).
4. Select your desired resolution. I chose 800x600 and am satisfied with it.
5. You may or may not want to activate "remove hud rectangle". I didn't.
6. Activate the patch by clicking on "Change Options".
7. Run the Game / Loader and choose "Settings".
8. There are three buttons on the upper-right side. Click the one on top, which are the "Performance Settings".
9. Click on the down-arrow on the upper-left side once and you will be able to set the resolution. Choose the same one you applied with the patch.
10. Click "OK" on the bottom and start a game.
(Further information can be found in the textfile (README_Z.txt) included with the patch.
Hope this works for you, as it did for me. Please report back, if there are still problems! :)
For me, there was no "change options" button but all your other steps helped me get the game running full screen, thanks. :)