Do you have clustering/load balancing in your environment? We had an issue with report subscriptions sometimes failing, and it turned out that we had two servers in the cluster that weren't synched up, so only one of them knew about some of the the subscriptions. If the good one was live, everything was fine, but if it switched over to the other server some subscriptions stopped working. Getting both servers upgraded to the same settings fixed the issue. Your issue is likely something different, but I thought I'd toss that out just in case it leads you somewhere useful.