Did you delete the account also or do you still have access to it?
If you have access to the account, ensure the domain is not only removed from the site, but also from Netlify Domains (via the Domains in the main navigation) the try readding the domain.
If you no longer have access to the old account, you will need to verify ownership of the domain as outlined in the following support guide.
Once you have done this, Netlify will release the domain for you to use again.