Successfully deleted bucket still claims to be there (aws-cli)

I deleted my bucket with aws s3 rb s3://BUCKET_NAME --force and it succeeded. The bucket is also not shown in the bucket list. However, when I try to deploy my cloudformation stack (which tries to create the bucket), I receive an error, claiming the bucket is still there.

Note: When I try to delete the bucket again I receive the error fatal error: An error occurred (AccessDenied) when calling the ListObjectsV2 operation: Access Denied