I once encountered such issue.
Maybe not in the same context :
Actually, I had a nice surprise with my smart playlists recently. It's a
different issue than yours. My iPod is a 2G model which has never had the
ability to update smart playlists on the fly as do the more recent models.
It only updates the smart playlists when the iPod is synched with my Mac,
which works fine for me.