I wonder if iOS Bluetooth scanning is slowing down when your app is in the background such that it appears that events never fire because they are just taking so long to happen. Rebooting may speed up the cycle.
One way to force a Bluetooth LE scan cycle to look for iBeacons is to run a different app in the foreground that uses the CoreLocation iBeacon ranging APIs.
Try installing Locate for iBeacon, then as soon as your app appears to be not getting notifications in the basckground, launch Locate for iBeacon and tap Locate iBeacons. Do you see iBeacons? Does your background app get a notification?
If this works, then repeat the test and instead of using the Locate app to force a scan, just wait (an hour if needed). See if you eventually get your notification anyway, and note how long it took.
Edit: it appears that this is a case where iOS stops looking for iBeacons entirely requiring a reboot. See related question below.
iBeacon: didRangeBeacons stops getting called, must reset device for it to work again