Adding a user trough the following PS command line works just fine:
Set-SPUser -Identity "Domain\LoginName" -Web $Web.Url -Group "GroupName"
The problem occurs when the user is deleted and then the above command executed again. No exception throw, but the user is not added. Closing the PowerShell console (or in the PS editor) and running again the command still doesn't work.