When executing the generated SQL statement in MySQL it gave me
The SELECT would examine more than MAX_JOIN_SIZE rows; check your WHERE and use SET SQL_BIG_SELECTS=1 or SET MAX_JOIN_SIZE=# if the SELECT is okay
To fix that I had to call $wpdb->query( 'SET OPTION SQL_BIG_SELECTS = 1' ); right before calling WP_User_Query.