Hi Scott, I have run into similar delays as you describe. I have published MXDs on our live server that have table joins or spatial views to non-spatial data in SQL Server and there is an inherent slowness to querying this data. I have even tried to build JSON queries to these services via REST, hoping that removing the spatial component would increase performance, but they are still slow. I came to the following conclusions:
1. ArcGIS Server must create a lot of database overhead when it performs queries.
2. In my situation, the live server is querying through a firewall, so there may be some sort of port delay or something like that.
The solution I came up with was to install a MySQL database locally on my ArcGIS Server web server and bulkload data that I wanted to join to my spatial layers. I built PHP queries that would pull data from the map service and use it to query the bulk loaded data in MySQL. Since the requests didn't have to go through a firewall or to any other server they were lightning quick. I even created an autocomplete address form that contains over 150,000 address records that is responsive to the keystroke. In the future I will not use ArcGIS Services to serve non-spatial data that can just as easily be loaded to the web server and be queried with PHP.
Hope this helps.