When each push notification comes in, you would invoke a "StartServiceAt" specifying a time that would be later then the next expected push notification should arrive. And when the next push notification comes in, you will specify another StartServiceAt time in the future (which clears the previous set time), and so on.
So, if the push notifications keep coming in, the StartServiceAt time should never trigger. But if the service does start, then that means a push notification didn't come in in time.
NOTE: The StartServiceAt may not run exactly at the time you specify, so just keep this in mind.