The deleted characters do count towards the limit until they are actually gone (takes a few days.) So if your slots are full and you try to delete one - you won't be able to make a new one right away. You'll have to wait for it to completely be gone.
Indeed 7 chars per server on one account and the deleted toon only goes away after a countdown period of 7 days. Once it's gone you are free to create a new one. So basically as answered by the previous two players :)