Annemarie,

It depends if the leavers left in the current PAYE year or not. If they left during the current PAYE year then you'll need a bureau licence, because the limit of 30 is per PAYE year, not per processing run. You'd need a bureau licence to do the year-end filing of more than 30 employees.

But if they left in a past PAYE year that you've already filed online then you can remove them.

1. Create a new payroll in the employer file
2. Drag the unwanted employees to the new payroll
3. Once they're all in the new payroll you can delete it in its entirety (click the red button at the top of the form)

Probably because you've recently upgraded from a version of the software that wasn't performing the check to the current release, which does perform the check.