Under your Service you created on ARCGIS Server there is a spot that you can change the maximum number of records returned by the server. I think the default is like 1500. If you change this to the be greater than your number of records you can get everything back. Of course there is going to some delay before the autocomplete loads. Below is a picture on where you can find this setting.
[ATTACH=CONFIG]12095[/ATTACH]
Hope this help you in your problem.