wp_dropdown_users() Optimization

Thanks a lot for this great plugin which adds good optimizations for larger sites. After analyzing many different cases on our WordPress installation the following query caused by wp_dropdown_users() is very slow with the optimized table structure:

SELECT wp_users.ID,wp_users.user_login,wp_users.display_name
FROM wp_users
INNER JOIN wp_usermeta
ON ( wp_users.ID = wp_usermeta.user_id )
WHERE 1=1
AND ( ( ( ( wp_usermeta.meta_key = 'wp_capabilities'
AND wp_usermeta.meta_value LIKE '%\"edit\\_posts\"%' )
OR ( wp_usermeta.meta_key = 'wp_capabilities'
AND wp_usermeta.meta_value LIKE '%\"administrator\"%' )
OR ( wp_usermeta.meta_key = 'wp_capabilities'
AND wp_usermeta.meta_value LIKE '%\"editor\"%' )
OR ( wp_usermeta.meta_key = 'wp_capabilities'
AND wp_usermeta.meta_value LIKE '%\"author\"%' )
OR ( wp_usermeta.meta_key = 'wp_capabilities'
AND wp_usermeta.meta_value LIKE '%\"contributor\"%' )
OR ( wp_usermeta.meta_key = 'wp_capabilities'
AND wp_usermeta.meta_value LIKE '%\"wpseo\\_manager\"%' )
OR ( wp_usermeta.meta_key = 'wp_capabilities'
AND wp_usermeta.meta_value LIKE '%\"wpseo\\_editor\"%' ) ) ) )
ORDER BY display_name ASC

We are seeing query times from 4 to 8 seconds with 4 million records in wp_usermeta. The queried values should be in an index but something seems to go wrong.

Any idea how to optimize this?