It appears to be feasible!
I found this article in which a "cooking expert" gives a specific recipe:
Frozen egg tempura
Remove the shell of a frozen egg and cut the egg in half lengthwise without thawing. A peeled egg is slippery, so put a paper towel on the cutting board before you place the egg on the board. Lightly flour the halves of the egg all over, and dip it in a mixture of three tablespoons of tempura flour and two tablespoons of water. Deep-fry the egg in oil heated at 160 C for about three minutes.
They're not too specific about the results, but I imagine they'd have mentioned if it exploded or anything!
This answer mentions doing essentially the same thing for a scotch egg:
Freeze the raw egg in its shell, de-shell the frozen raw egg and wrap the sausage meat around it whilst it is still frozen. This can be difficult as the egg's albumen defrosts quickly. Coat in flour, egg and breadcrumb. Fry till the scotch egg floats and the crumb is a deep golden brown.
It's the only way I know that gives a soft runny yolk every time.
I don't know what frying temperature was used, and it's got sausage and breading around the egg rather than just tempura batter, but it's a deep-fried egg, starting from raw/frozen, and produces a soft yolk.