Popping the battery out of the AirTag doesn't remove the pairing. All of the logic for when notifications are sent are in the app and what Apple stores in their server-side database in the cloud.
Un-pairing and re-pairing it may help with the notifications, but it could be a corner-case that
@mikecwest is hitting.
Everyone that's running into issues should be using the feedback app (if they're running beta iOS) or Apple's feedback site (
https://www.apple.com/feedback/airtag/) to report these issues to Apple - it's the only way that they'll get fixed.