I am not sure if this will work, but it is worth a try.
Go to:
http://www.palm.com/us/support/index.html
Choose "Palm 500" from the Palm More choice
Then select "Download Palm Desktop" under Windows Hotsync
choose M500 again
and choose Windows 95
I don't know if this will work, I used the disk that came with my M500.
But I think it might.
If that works, don't sync you palm with that version. Just bring up the desktop, exit it, then try to install the new version before you sync.