bad performance on 3 connected queries with counts

Hi, could somebody help us with this issue..

We’ve three queries in production and they are run for each search.  The first returns the paged search results.  The second returns a count with security filters applied.  The third returns a count without security filters applied.  If the count in the third query is higher than the second, a message is displayed.  The two count queries are very inefficient as they require scanning of all records on huge tables.  Implementing a fix to remove the display of the count from the search grid eliminates the need for the second query but not the third.  This is why when we