The index is working as designed, it's just filled with a lot of false matches which have to be explicitly tested against the filter to be weeded out. The objectclass index provided 355545 candidates in the range of 228 thru 355772. Some other search term provided (355755-112277) candidates, leaving the range from 112277 thru 355755 needing to be tested. If this search takes too long, then you need a larger entry cache.
I tried to increase the cachesize and idlcachesize to 100000 and restarted the slapd, but it did not help.
Tim