What is known about the number of labeled regular graphs on n vertices? The sequence does not appear to be in the OEIS.
For fixed $k$, the problem of counting $k$-regular labeled graphs is not intractable at all; the counting sequence is P-recursive, so in principle the sequence is (up to a constant factor) as easy to compute as it could be. (But the complexity grows quickly with $k$.)
For $k\le 5$, see I. P. Goulden and D. M. Jackson, Labelled graphs with small vertex degrees and P-recursiveness. SIAM J. Algebraic Discrete Methods 7 (1986), 60-66.
and for P-recursiveness in the general case see my paper
Ira M. Gessel, Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A 53 (1990), 257-285.