I actually feel like I'm spamming all the forums for the games I have problems with, since my solution to all of them has been the same - dgvoodoo. http://dege.freeweb.hu/dgVoodoo2/dgVoodoo2_55_4.zip
Installing the dgvoodoo .dll files into the root of the Amerzone folder got the game running for me.
I had been using dxwnd which did get the game running but the game being in windowed made it horrendous to actually read the text in letters etc. as it was too small.
dgvoodoo lets the game run fullscreen, downside is the splash mark on the bottom right covers up some of the text while reading the letters etc.
Oh, and it also plays fine with DEP still set to the standard setting, so no fiddling around with it like in the solution you already tried (changing DEP didn't work for me either).
You can remove dgvoodoo splash mark, btw.