The problem is probably not WMP but the Microsoft MPEG-1 codec. The straight forward solution other than using a decent player is to use a better codec pack - ffdshow, it feeds WMP through the operating system level. Besides the seek issue you'll probably get better playback performance, and it doesn't require any end-user involvement - they continue to use WMP as usual.
If touching the end-user's machine is entirely out of the question then you'll have to transcode the video to something else. You'll probably get the best results (file size, quality, compatibility) by transcoding to H.264/AAC (mp4), although the encoding process is heavier/longer than alternatives such as MPEG2. You'll need for that ffmpeg and start with:
ffmpeg -i mpeg1filename outputfilename.mp4
There are tons of options that will affect the transcoding quality and speed, and much of your success will depend on trial and error with your specific footage. All that said, your first choice should be to install ffdshow on the end-user machine.