Looking through the software-center revealed some interesting possibility to speedup the loading time:
Directly getting the icon from the database instead of creating a softwarecenter-appdetails object
brings the time to load the apps from 2sec to 0.2sec. 

I think a factor of 10 is a good start to make the autocompletion loading smoother :-)