No, AFAIK, none of the iPods, including the iPhone, are able to do smart playlists that update themselves while on the iPod. So the only real solution I know about is to sync more often.
Otherwise, I guess you could do some trickery along the following lines:
- Create a smart list of recently played songs with the constraint that they also appear on the playlist of songs that your Shuffle syncs with (the master one that has all the songs on your Shuffle)
- With or without a macro, set up your iTunes so that your shuffle songs have some identifier, like they all have a certain rating (if you don't generally use ratings) or something, and then set that as a criteria for your smart playlist.
In both cases, the playlist will still use the songs whether they were played on the iPod or in iTunes, but it will limit the songs to the iPod's songs....