We have measured the beam-normal single-spin asymmetry $A_n$ in the elastic
scattering of 1-3 GeV transversely polarized electrons from $^1$H and for the
first time from $^4$He, $^{12}$C, and $^{208}$Pb. For $^1$H, $^4$He and
$^{12}$C, the measurements are in agreement with calculations that relate $A_n$
to the imaginary part of the two-photon exchange amplitude including inelastic
intermediate states. Surprisingly, the $^{208}$Pb result is significantly
smaller than the corresponding prediction using the same formalism. These
results suggest that a systematic set of new $A_n$ measurements might emerge as
a new and sensitive probe of the structure of heavy nuclei.
