timppu: Now I am thinking was there some version of Virtua Fighter PC for such hardware which was still-born upon release? Was that early 3D accelerator even from NVidia? Dang, I can't remember.). EDIT: Ok, I think Amok got it. There were probably indeed some earlier, e.g. Matrox, "3D accelerators" which got some special versions of certain games.
Yes Virtua Fighter Remix on PC came bundled with i think a Diamond Edge(NV1) 3D graphics card in early 1996, you are right in that it was released by Nvidia, other early 3D accelerated cards were the Matrox Millennium/Creative Labs 3D Blaster which was Vesa Local Bus.
Nascar Racing had a 3D accelerated version bundled with the Matrox Millennium I graphics card but this card really didn't have full 3D accelerated features but was limited.
I would say Nascar Racing released in 1995 was the first PC AAA 3D accelerated game, it ran really well on the Matrox Millennium I graphics card.
Some other early 3D accelerated games released for the Creative Labs 3D Blaster were Magic Carpet and Flight Unlimited, these might be in contention too for the first PC AAA 3D accelerated games but i think Nascar Racing just beat them.