I have been through the exact same scenario as yours in my virtual environment with Protect 9.1.4511 and I cannot reproduce this issue. After renaming the patch group and initiating another scan straight away with the Scan Template using this patch group the patch excluded remained excluded from the scan.
Which version are you running ?
If I were you I would check if the scan before the deployment occured was run with a different template than the one you thought you used.
It may be worth that you open a case with Support in order to help you out with this.