I have rules setup for both type of tokens and they work fine on my system.
If a token is deallocated it will be quarantined for 7 days. Once available again then when you add a new user your rule should kick in and allocate it to them.
Can you provide a screen shot of your rules?
Also, what user directory connector are you using to sync users?