At first I had troubles running NFS4:HS on V5 5500 AGP, but now I seem to have better view of the problem. Its not the game itself, its Voodoo. Anti aliasing doesnt work in Glide mode. I am using 3dhq drivers which have been awesome so far, but there might be a driver conflict between them and V3 3500  official driver, since I'm hot-swapping them according to my prefferences.

I'm running Win 98. Tried Glide AA in UT99, NFS2SE, NFS3, NFS4:HS and it doesnt work. Every other setting(mip mapping, LOD...)
from 3dhq drivers works.

Any ideas on how to return AA to glide (without reinstalling windows)?

try using set FX_GLIDE_AA_SAMPLE=4 via batch file.