If you choose to post a listing on a directory, I think it is worth your while to post in those directories which actually rank on the first few google pages. I briefly did a search for "piano tuning Illinois". There are plenty of free directories with free listings, such as yelp, yellowpages.aol, bing, angies list etc etc. I looked through the first 150 google listings (15 pages) and pianotunerbystate did not come up.
"Leave no stone un-turned", of course, but turn the big and important ones first.