Serverless: The specified bucket does not exist

I needed to delete the stack from cloud formation, once done I was able to re-run serverless deploy successfully.

Yes the serverless works like that only. When you deleted the s3 bucket it was not deleted from the stack entry hence it was failed. We should delete Stack entry as well from it if we are deleting the S3 bucket. From error handling we can also check if bucket exists or not.