The standard approach to bundle routing in delay-tolerant networks with predictable contacts uses a graph traversal algorithm to search for paths where the graph’s nodes represent the presumed and non-expired contact opportunities and the edges the waiting time for the next contact to occur. However, unforeseen systemic issues may introduce random contact holdups, i.e., the start time of certain contacts may be delayed, which may lead to lower performance than anticipated. An analysis of random contact holdups and their impact on the probabilistic optimal routing of bundles over parallel, non-overlapping substrate paths are provided. The study brings new insight into the consequences of unforeseen divergences between the planned contacts and their realization, which may help to improve the design of future DTN protocols.