Since there is no way to reject a transaction, every person who attempts to execute a scheduled call will have to pay some small amount for the transaction. If the service is implemented as a first call wins sort of thing, then all of the people who tried and failed would be out the gas cost of that transaction. For calling contracts to be profitable, these costs would have to be covered somehow, otherwise there is no incentive for people to execute calls.
So, this cost would have to be offloaded onto the people scheduling calls which would cause a significant increase in the overhead of scheduling a function call.
The alternative solution I came up with was having a caller pool. The people executing the calls are guaranteed a window of time where they can call the contract and also incentivized (by their bond) to fulfill that duty lest the next person in the pool claim their bond.
I'm open to alternate solutions to this problem.