First of all, thanks for the suggestions. I’m writing them all down.
Regarding Nevada, I didn’t use Stop In Nevada because the only time the name is mentioned is during that line, which is the title of the song. If he’d said Nevada somewhere else, without “Stop in” in front of it, I’d use it.
Same with New York, and New York State of Mind.
The Bee Gees’ Massachusetts has the state, but that’s it for the title. Too easy. No other words in the title.
Oh, and C3? Thanks for reminding me that St. Robinson In His Cadillac Dream by Counting Crows mentions Maryland.