"If there's a state without a listing, omit it from the state checkboxes, or grey it out. "

This is not true, there are listings in every state. Just not for EVERY keyword. Make sense?
Look we can't win in every situation. If someone can't find something and they are not educated, all we can do is hope they come back.