Are you using custom itemRenderers? If so, you probably need to optimize them (start with UIComponent rather than Canvas, for instance).
There must be something else going on here.
Retreiving 750 records from a webservice should take no more than a few seconds!
Also, if you're populating your dataGrid no more than let's say 50 records are displayed at a time, so that should take no more than 1 second!.
What are you doing with the data once it get's returned from your webservice?
It doesn’t matter how many records, what matters is how many attributes and sub-objects. One customer returned 100 records, each with a transaction history of some 10,000 transactions, although the transactions were not displayed in the datagrid (it would be later in the detail view). Then the app was configured to convert the records to typed objects. As one would expect, it took forever. You might have to create a custom converter or just use the SOAP/XML.
harUI is right! You probably retreive all info at once! When you fetch a list from the server to display in the datagrid, just retrieve the info that should be displayed in your dataGrid. Then, when you click on a single row in the dataGrid, retrieve the detail of that one single record.