Ha! I finally figured this out, and it makes iTunes practically usable now!
If you have songs in a playlist, and you want to delete them from from the Library or iPod, not just from the playlist, select them and hit Ctrl-Shift-Del.
I manage my MP3s myself, and I have two different size iPods, so I can’t just chuck everything in iTunes and slap ‘em all on the iPods. I run a script that generates M3U playlists from the various directories in my collection, then I import them into iTunes. I have a smart playlist that looks for songs that aren’t in any of those playlists, which means they’ve been moved or edited, so now I can delete them straight from there, instead of rating them with one star and then sorting the library by rating. I still have to redo the smart playlist every time I update another playlist, since it looks at some invisible identifier instead of just the playlist name.
I don’t know why Apple has to make their software so dumb that advanced users are actually prevented from doing what they want. With just a few more (or at least documented) features, it really could be everything for everyone.