It turns out that the situation for licensing music is not quite as bad as I had thought once you know the system, but there is still a lot of room for improvement. There are two companies, BMI and ASCAP, that are the main gateways to the music industry's licensing machinery. Thay have searchable on-line databases that will give you the name and contact information for the publisher of most popular songs, including the ones I'm looking for.
From there the procedures vary by company. In my case I'm dealing with two different publishers, both of which require you to send in a written request for a quote by fax. Why they don't have a web page set up for this in this day and age is beyond me (but is pretty much in keeping with the music industry's general attitude of being too important for their customers). Maybe there's a business opportunity here.
One of the things I've been told is that the quotes for licensing music for movies vary by term (which is to say time period) and territory. Since my film isn't in production I have no idea what the term or the territory might be. We'll see how much of an obstacle that presents to getting them to name me a price.