So why is this a valid proof for all resistors in parallel
First, you have an error in your question - the equivalent resistance is
$$R_P = \frac{1}{\frac{1}{R_1} + \frac{1}{R_2}}$$
Now, the voltage across the two parallel resistors is what it is regardless of how the voltage comes to be.
However we choose to label that voltage is immaterial, thus, we can arbitrarily label the voltage across the parallel resistors as, e.g., \$v_P\$.
Now, and again, it does not matter how this voltage comes to be, the voltage variable \$v_P\$ is the voltage measured across the parallel resistors when "red" lead is placed on the "\$+\$" labelled terminal and the "black" lead is on the "\$-\$" labelled terminal.
Thus, by Ohm's law, the current through each resistor is
$$i_{R_1} = \frac{v_P}{R_1} $$
$$i_{R_2} = \frac{v_P}{R_2} $$
So, the total current is, by KCL,
$$i_P = i_{R_1} + i_{R_2}$$
and the equivalent resistance is defined as
$$R_P = \frac{v_P}{i_P}$$
thus,
$$R_P = \frac{v_P}{i_{R_1} + i_{R_2}} = \frac{v_P}{\frac{v_P}{R_1} + \frac{v_P}{R_2}} = \frac{1}{\frac{1}{R_1} + \frac{1}{R_2}}$$
Again, if we replace the two parallel resistors with a resistor of resistance \$R_P\$, the current through the equivalent resistance will be identical to the sum of the currents through the two parallel resistors.
Best Answer
One way to attack this is to realize that R1 is connected between two Thevenin sources. R5,R2 form a Thevenin source, and so do R4,R3. Put "test" voltages at both connections to the net, then solve for the parameters of the two Thevenin sources. Using nice numbers for the test voltages, like 0 and 1 V, makes the arithmetic easier later.
Connect R1 between the two sources. Now you only have a string of 3 resistors in series with known voltages at each end of the string. Solve for the voltage at the two internal points. Those are the voltages of the two internal nodes in the original problem.
By knowing the voltages at the two internal nodes, you can find the current the whole net is drawing. That is either the sum of the currents thru R5 and R4, or thru R2 and R3. Both should be the same. It would be a good idea to compute both and verify that they are indeed the same. If not, you made a mistake somewhere.
Now you know the voltage across the net and the current thru it. You find the equivalent resistance of the net by using Ohm's law.
There are more direct ways to reduce this problem, but this way gives you some insight into what is happening, and provides oppertunities for sanity checks along the way. You can also use this method to derive a direct formulaic answer.