Intrinsic variability in electromigration (EM) lifetimes mainly occurs due to the material's microstructure. This work demonstrates how to account for such variability and its impact on EM-induced failure. A Markov Chain model was developed to act as a surrogate model for continuous degradation predictions capturing the same variability observed in experiments or physics-based simulations. Moreover, a multi-fidelity approach and tailored Monte Carlo sampling are employed to develop fast models for reliability without compromising accuracy, achieving an 87% reduction in simulation time. The accelerated simulation framework was used to create training data for a predictive neural network (NN) to estimate the current density limit for EM compliance checks, jmax, and to investigate a model-predicted favorable metal barrier thickness. For the investigated shunting-guaranteed case, the model predicts a nominal optimum near a metal barrier area ratio (BAR) of ~16% of the total trench area.