Am I right in thinking that you are referring to your company profile in the Management Console?
When you remove a user from your company profile, this will only dissociate the account from your profile. The account will not be deleted completely; it will continue to exist as a free account.
That is why it is not possible to create a new account with the same email address in that case.
If you want to add the user once again to your company profile, please use the button "Add existing account" in the User management tab of the Management Console. The Management Console will display a link which you can then send to your colleague. He will only have to click on the link, sign in to his account and give the email address of one of the administrators of your company profile (e.g. your email address). Once that is done, he will once again show up in your User management.
Please also take a look at this Knowledge Base article, which includes some helpful screenshots: