There are two possible reasons for the title issue. The source of one is RecId sequence and the other is the Number sequence used for PayrollPayStatement. The first one I already posted in my article.
For the second one, we need to find the exact number sequence assigned via Payroll parameters as per the screenshot below and then choose View Details to reach the number sequence form:
There we need to either clean up specific number sequence number, or all available free number sequence by Delete Record or Alt+F9 key after selecting the record(s). The screenshot is as below:
Hopefully this will resolve the issue.