I don't own an mp3 player (gasp!), but I wouldn't be surprised if they didn't track when a song was played, but only incremented a play counter without date/time information.
If this is so, a compromise feature would be to add the tracks "time played" information as the moment when that track was resynched with mediamonkey. (I know this is probbaly beyond the capability of scripting at the moment, but you never know.)
You will probably get a few tracks with identical play times; would this be a problem?