You didn't say where you've looked already, but the Internet Archive has two potential sources.

The Software Collection doesn't contain it directly, but if you can identify a magazine cover disc with it, they may have that.

Otherwise, you can do a historical searches - it doesn't seem to do phrases, but it did highlight the now-offline dailymp3.com which is audio-focused but may contain it in its updated software lists, or fiddle with search terms to see if any other relevant sites come up.

The X-Micro Video MP3 user manual says it came with that. The archived X-Micro download page doesn't have a link for the XMP3R, but this dodgy looking foreign driver site has an 11.8MB download that may or not just be drivers/malware.

You could also try getting in contact with random strangers Fernando or BlueSweety3 and see if they have a copy of it

...and in trying to recall what that other format was, I stumbled over this:
https://web.archive.org/web/20100815084506/http://www.kingston.com/support/PORTABLEMEDIAPLAYER/Transcoder.asp

"The PMP Transcoder is the KPEX100 tool that enables you to convert WMV, ASF, MPG, and AVI video files into the supported MPX format."

Had to download via Curl because Chrome sucks, but it did successfully convert an AVI - hopefully MPX is a single format, and doesn't do player-specific codec stuff or whatever...