One can obtain a little more in Geoff's situation, where $O_p(G) > 1$. Write
$U = O_p(G)$ and $U_i = U \cap H_i$, so $U_i = O_p(H_i)$, as Geoff showed. In particular, $|U_1| = |U_2|$. Note that the $U_i$ are proper in $U$. I claim that 
$U = U_1U_2$. 

First, observe that $U_1 \triangleleft G$ since $N_H(U_1)$ contains $H_1$ properly because $N_U(U_1) > U_1$. Since $H_1$ is maximal, $U_1 \triangleleft G$, as claimed. Next, $U/U_1$ is $G$-chief by the maximality of $H_1$, and in particular, $U/U_1$ is abelian. Since $G = UH_2$, it follows that $H_2$ acts irreducibly on $U/U_1$. Now $H_2$ normalizes $U_2$, so it normalizes $U_1U_2$. Since $U_1 \subseteq U_1U_2 \subseteq U$, we have either $U_1U_2 = U_1$ or $U_1U_2 = U$.

Since $|U_1| = |U_2|$, the first possibility yields $U_1 = U_2$, and this is a normal subgroup invariant under an isomorphism from $H_1$ to $H_2$, so we have that the $U_i$ are trivial in this case, and $U$ is minimal normal in $G$. Since $G = UH_2$, this implies that $H_2$ is maximal, contrary to assumption. We thus have $U_1U_2 = U$, as claimed. In particular, this yields $G = H_1H_2$.

But where do we go from there?

---
OK, now I know where to go. I can finish the proof in the case where $O_p(G)$ is nontrivial.

Assume $G$ is a minimal counterexample. Let $D_2 = H_1 \cap H_2$ and let $D_1$ be the image of $D_2$ under some isomorphism from $H_2$ onto $H_1$. Thus $D_1$ and $D_2$ are isomorphic subgroups of $H_1$ with $p$-power index equal to $|G:H_2|$. I claim that $D_1$ is maximal in $H_1$ but $D_2$ is not, and also $O_p(H_1) = U_1 > 1$. Since $G$ is a minimal counterexample and $H_1 < G$, this will be contradict the minimality of $G$.

First, to see that $D_2$ is not maximal in $H_1$, choose a subgroup $X$ with
$H_2 < X < G$. Since $H_1H_2 = G$, we deduce that $D_2 = H_1 \cap H_2 < H_1 \cap X < H_1$, as wanted. 

Next, to show that $D_1$ is maximal in $H_1$, it suffices via the isomorphism to show that $D_2$ is maximal in $H_2$. Note that $H_1 = U_1D_2$ by Dedekind's lemma. Suppose $D_2 < Y < H_2$. Recall that $U_1 \triangleleft G$, so $H_1Y = U_1D_2Y = U_1Y$ is a subgroup. Also, $|H_1Y:H_1| = |Y:D_2|$, and it follows that $H_1 < H_1Y < G$, contradicting the maximality of $H_1$. 

Now we need a proof (or counterexample) in the case where $O_p(G) = 1$.

----
My argument proves that if $H$ is paradoxical in solvable $G$ with $p$-power index, then $O_p(G) \not\subseteq H$. I did $not$ actually prove that $O_p(G) = 1$, but we do obtain this conclusion in a minimal counterexample. 

Robinson has used my contribution and some deep theory to completely solve the problem for groups of odd order. (I am impressed.) We can also obtain some easier consequences. For example:

THEOREM. If H is supersolvable, then it cannot be paradoxical in a solvable group.

PROOF. As usual in a minimal counterexample, there is no nonidentity normal subgroup of $G$ contained in $H_1 \cap H_2$ and invariant under an isomorphism from $H_1$ to $H_2$. Now as $H_1$ is supersolvable, it has a nontrivial normal Sylow $q$-subgroup $Q$, and we know $q \ne p$, so $Q$ is Sylow in $G$. If $Q$ is normal in $G$ it is also Sylow in $H_2$ and is invariant under an isomorphism from $H_1$ to $H_2$, a contradiction. Otherwise, $H_1$ is the full normalizer of $Q$. A Sylow $q$-subgroup of $H_2$ is conjugate to $Q$ so its normalizer in $G$ is conjugate to $H_1$ and contains $H_2$. It follows that $H_2$ is maximal.