Job with WithoutOverlapping never starts after one fail

I recently had an issue with one Job that has the middleware WithoutOverlapping where after one fail, the job never starts again.

I tried using releaseAfter and expireAfter and it doesn't work. It is always failing with this message:

Illuminate\Queue\MaxAttemptsExceededException: App\Jobs\TestJob has been attempted too many times or run too long. The job may have previously timed out. in {my-path}/vendor/laravel/framework/src/Illuminate/Queue/Worker.php:750

I notice that if I remove the WithoutOverlapping it works. Any idea what is causing this?

I'm using Laravel 8, PHP 8.1