I have managed to get my Ipod Shuffle (2nd gen. orange) to be completely full - 0 bytes free space. This was actually quite an accident, as I was just clearing some songs off to make room for new ones, when I realized that I had done this perfectly.
To update my shuffle, rather than using iTunes, I use a simple open-source python program called iPod Shuffle Database Builder. This little (19KB) program allows me to treat my shuffle just like a normal mp3 player, dragging and dropping the songs on using Windows Explorer (or Nautilus if I'm in Linux). This means that I don't have to open up the great memory hog that is iTunes - I don't even have it installed since I wiped my computer. It also means that my songs are stored in a logical folder hierarchy that makes it easy to offload them to my friends' computers. Naturally, it also allows to me to get songs from other people directly. For a power-user with a shuffle, this program is a must-have.