We disabled the approval requirement(in the Bookings admin settings for our tenant) so our staff do not need to approve anything. I don't think they would receive any email regarding approval.
We finally resolved this by removing all the staff from the bookings calendar and adding them back(multiple times). Then we encountered a different issue, 1 of the 5 staff was not found when trying to add him back to the calendar. We deleted the calendar and started again. Still only 1 staff was not found when trying to add him back to the new calendar.
Finally we were able to add him by typing his full email address in the 'add staff' drop-down, then clicking the 'search directory' link. Eventually he showed up and we were able to add him to the calendar. The other 4 staff would automatically populate the drop-down after typing just the first 3 or 4 characters of their email or by typing their name.
I don't know what would have caused this because we had been using Bookings without any issue for well over 15 months. All our users/staff are created the same way and receive the same license and there was nothing out of the ordinary operation for managing our staff. Seems like a random glitch.
Thanks for your reply, I hope this helps others having similar issues.