Random unique string against a blacklist

I want to create a random string of a fixed length (8 chars in my use case) and the generated string has to be case sensitive and unique against a blacklist. I know this sounds like a UUID but I have a specific requirement that prevents me from utilizing them

1. some characters are disallowed, i.e. I, l and 1 are lookalikes, and O and 0 as well

My initial implementation is solid and solves the task but performs poorly. And by poorly I mean it is doomed to be slower and slower every day.

This is my current implementation I want to optimize:

private function uuid()
{
    $chars = 'ABCDEFGHJKLMNPQRSTVUWXYZabcdefghijkmnopqrstvuwxyz023456789';

    $uuid = null;
    while (true) {
        $uuid = substr(str_shuffle($chars), 0, 8);

        if (null === DB::table('codes')->select('id')->whereRaw('BINARY uuid = ?', [$uuid])->first())) {
            break;
        }
    }

    return $uuid;
}

Please spare me the critique, we live in an agile world and this implementation is functional and is quick to code.

With a small set of data it works beautifully. However if I have 10 million entries in the blacklist and try to create 1000 more it fails flat as it takes 30+ minutes.

A real use case would be to have 10+ million entries in the DB and to attempt to create 20 thousand new unique codes.

I was thinking of pre-seeding all allowed values but this would be insane: (24+24+8)^ = 9.6717312e+13

It would be great if the community can point me in the right direction.

Best, Nikola