Unfortunately there’s no ‘fix’ for the described behavior that I’m aware of.
However, there are a lot of free/paid utilities that will not only do what you need, but also improve the experience overall.
I could list you a dozen utilities but instead I will let you do your homework and decide what’s best for you. This list contains an important amount of utilities for iTunes controlling.
I can tell you which ones I use and my experience with them.
1) Coversutra: It’s a very well designed paid application. You can check their website for a more comprehensive summary (and a trial). The developer (Sophia) reads the suggestions and bug reports.
Pros: It’s very good for searching, very good. Think of a spotlight music dedicated. You can easily switch between playlists, songs, artists, etc. All from the menubar. (I activate it with shift + cmd + space. It also has a controller where you can define your keys for showing album art, define song rating, next, prev, pause, etc. The typical controller stuff. You will rarely need the keyboard.
Cons: Although it has been optimized several times and results come extremely fast, scrolling the results is not as fast as one would expect. Sometimes certain actions might need a “click”.
All in all, it’s a product that works fantastically for me.
2) Launchbar: I use Launchbar for everything, and sometimes for music too. Since it has iTunes support, you can easily type the name of a song/artist/list and will happily play it. What it does is create a playlist called Launchbar and whenever you make a selection, it adds the relevant songs to that list, therefore when you pause/play, things work normally. You can also do the same things (pause, play, next) from launchbar.
Pros: It’s also very fast and it does a lot of things (can’t live without it!)
Cons: Might be overkill for a song launcher/iTunes controller only.
When iTunes shuffles through a playlist, library, or other list, it only will shuffle among items for which the "checkbox" column is checked. By default, this would include all the items in your library; only if you uncheck the box for a song would that remove it from the list of songs to shuffle.
It sounds as though your library is set up with all the songs unchecked. If no songs are checked to be included in shuffle, one gets the behavior you describe. The solution is to go to your library and make sure all your items are checked, not unchecked.
You could use iTunes DJ. Select the playlist that you want from the list in the left-hand corner.
Then, you can right click on a song, and select "Play next in iTunes DJ"