I had the same issue with QBO. Deleted employees upon re-hire were not showing up on the Weekly Timesheet dropdown or Payroll/Profit Loss Statement.

Solution: Payroll Technical department had to 1. resync my account and 2. re-instate the deleted employee.

That solved it.