I have an interesting take of this situation. I have two computers, a 1.6ghz Pentium 4 running XP SP2 and a iBook G3 600mhz running OSX 10.3.8.
Now do to the smaller hard drive of my iBook, it has a 10.5 gig iTunes library. I keep a more complete iTunes library of 21 gigs on my PC. 98% of the iBook songs are on the PC, vice versa, 49% of the PC songs on the iBook.
I installed my 1GB shuffle on both machines (iBook first), it shows up on both machines in the iTunes playlist list under the same name.
Here's the thing, both machines recognize the shuffle. Both machines have different shuffle playlists. When I plug it from one machine into the other (P4 to iBook), iTunes will see which songs are supposed to be on the shuffle and remove all that are not present in the current iTunes library, but it'll leave the songs it expects to see. Same happens on the other machine, it'll immediately remove the songs it doesn't see in the library.
Yet, it will only start removing songs when iTunes is open. In the pref pane, there's an option to auto-launch iTunes. If the shuffle auto-launches iTunes, it will "fix" your shuffle's music. If the auto-launch is left off, you're welcome to plug in and move files, recharge without the re-sync and without changing your current shuffle playlist.
To recap my overly long explanation, install the shuffle on every machine, just ensure that the iTunes have the same songs in the alternate library.
Rock on.