Interestingly, the SP2 to SQL 2008 R2 wacked my search queries. The part where I had SELECT TOP( @PageNum * @RecCount ) now causes it to pull back random values.
I've since done several things. First was that I got rid of the SQL full text search matching. It was ludicrously slow. Second, I removed the TOP(@PageNum * @RecCount) part and in the final select added SELECT TOP(@RecCount) TotalCount, ...
Seems fast and easy.
Also, the following article talks about using a key seek method that appears to be very very fast: http://www.sqlservercentral.com/articles/paging/69892/