Are there any script triggers on the fields in question?
I have noticed sometime that typing can be sluggish in fields with the OnModify script trigger if you have a meaty script associated with it.
i have the same issue. And securtiy just checks one flag of a related table with only 30 records .. - auto-complete takes on first hit a delay of a couple of seconds then it catches up.
the context where it is worst is when entering data within a portal and allow creation of related records is checked for the portal's TO.
I fixed it by creating a new user in security. It has the exact same priviledges as the old one. When they log in with the new one, it zips along great. I have no idea why but it works now. I hope this helps somebody.