Wow this fixed my problem completely!!!
It would be useful to have the link to this codec on the FAQ.
Installing movie player from the FF7 CD didn't fix my problems, but this codec did.
This is what was wrong before I installed the codec:
(GeForce 2 MX 400, driver 56.72, Windows XP)
-Passed 8-bit textures, but no hardware rendering option available (fixed by 1.02 patch)
On no compatibility mode (on both hardware and software rendering):
-A black screen and FF7 exits.
Hardware rendering, compatibility mode
-Black screen (no video), plays sound of eidos movie, then freezes (or goes into the menu without video but with audio).
In Win98 compatibility mode, software rendering
-Videos upside down (then I installed the upside down patch) and the movies were twice the original size (so only the top left quarter could be seen).
-640*480 playback very very slow (2 FPS) on a PIII 733 MHz.
I hope this helps other people having similar problems

P.S. I could play the avi files in Windows Media Player fine before installing the codec.