You are correct. You have to start from scratch. The BES stores the PIN in the users mailbox so it has to be a new PIN in order to trigger per-pop. So you either need a new device or remove/readd to clear the pin from the mailbox. There is a reg key to bypass this, if you search the forum you should find it.
Once the user is reactivated and if email does not flow let us know. You may want to check the MAGT logs as well for that users email around the time the email was sent.