This paper presents an exact reliability analysis of von Neumann multiplexing using majority gates of fan-in A = 3,5,7,9,11, and the corresponding minimum redundancy factors R = 6,10,14,18,22. Such results are extremely important for a deeper understanding of von Neumann multiplexing (and its variations), especially when considering the expected unreliable behavior of future nano-devices and interconnects. The analysis confirms and augments well-known theoretical results, and is exact as being obtained using exhaustive counting. The extension of the analysis to the device level will allow us to characterize von Neumann multiplexing with respect to device failures for the first time. The results are very timely and are also explaining a strange (non-linear) behavior of von Neuman multiplexing reported two years ago (based on extensive Monte Carlo simulations).