Unfortunately, we still weren't getting any search results. The problem didn't appear to be with the index, but I cleared the index and rebuilt it just to be sure. Still no results. I also noticed that there was nothing useful in ULS to help me track down the problem.
On a suggestion from a colleague, I created a new web application and associated it with the same search service application. I added some dummy content to that new web application and indexed it. When I ran a search from within that search application, I was getting results. Progress - now I knew that my search service application appeared healthy.
We decided to see if the problem was the content or the site itself. We took a backup of the content from the production web application and restored it to the new web application we had just created. We then rebuilt the index and ran a test. Search worked perfectly. So our problem wasn't the content.
Now that we had narrowed down the problem to our web application, we had a pretty easy fix. We waited for a maintenance window and then removed the web application. We then provisioned a new web application with the correct settings for our production environment and attached the content database from the original. After another rebuild of our index, we had working search results.