I have the same issue here.
I have (3678) Users with Unconfirmed Email Address and none of them show up in the Users > Unconfirmed admin menu.
I would really like a way to clear out these users without using the default WP menu, which only allow for removal of 10 at a time. I have tried removing users from the DB using PHPmyAdmin but also with no success.
Any Solution on offer?