I'm trying to figure out ASP.NET's
public object GetStuffMethod(int pageNum, int recordsPerPage, out int totalRecords)
I strongly recommend that you go the ObjectDataSource route.
If you are unfamiliar with this approach here are the basics:
1) Instead of manually setting the grid.DataSource property in the code behind, you add an extra element to the page . You set the DataSourceID of the grid to the id of your ObjectDataSource.
2) This is where you get real control. You create a new class and give it two functions "SelectRows()" and "GetCount()". You can put your logic in both functions and optimize to your heart's content. Feel free to use web services if that's what you need to work with, but under this method, you can call one to return rows and other to return the count.
3) use the ObjectDataSource's property editor to connect it to your class and enable paging. You're all set!
I strongly suggest you check out The Code Project's Example of using ObjectDataSource and GridView as this is clearly the intended way to support what you want.