Maybe it's parsing the THREAD response, but I don't know. It also is FETCHing messages for a hundred threads, no?
Fetching is extremely fast (0.004 + 0.000 + 0.003 secs). Could you explain, why there is 3 numbers? (in previous message I show you only the last one)
And is there in chance to increase performance without disabling threads?
Did you try setting sorting to None? You can consider enabling imap_cache.
$config['imap_cache'] = 'memcache'; did nothing (sure, memcached is running and configured for RC)