The first version of Windows PowerPoint that will embed video is 2010. Embedded videos will play in it and also in PowerPoint 2007 IF Service Pack 2 is applied (and presumably later SPs, if and when they become available).
I think embedded vids will play in the latest version of the free Viewer but not in earlier versions.
If you use QuickTime movies, QuickTime must also be installed on the Windows PC in order to play the video. You can make them more widely compatible by opening the presentation in 2010 on a PC with QT installed and using the optimize feature on the vids (which converts them into a format that doesn't require QT on the playback PC).