Two rectangles whose sum of areas is given
Assume all integers involved are even. This can be ensured by multiplying $P$ by 4. Here is an idea that should speed up the search. Let $p = \left\lceil\sqrt{P}\right\rceil$. If $p*p = P$ we are done. Otherwise, let $k$ be the minimum such that $\alpha =p*p-k*k \leq P$. If $\alpha=P$, we are done as $(p-k)\times(p+k)$ is the desired solution with perimeter $$4p$$. Otherwise, clearly $1 \leq k^2 \leq 4p$ (otherwise, $p$ would be smaller). But this implies that $k \leq c*P^{1/4}$, where $c$ is some small constant. This implies that $P - \alpha \leq c'*P^{1/4}$.  Thus, the solution with rectangles $$(p-k)\times(p+k) \text{ and } 1\times(P-\alpha)$$ has perimeter $4p + O(P^{1/4})$. Since $4(p-1)$ is a lower bound on the solution by the argument below (intuitively, the isoperemeteric inequality), this implies that search range is only of size $O(P^{1/4})$ (as far as the overall perimeter is concerned).

It definitely feels like this argument can be pushed even further... 

And Jeff is right - this is not necessarily too interesting as far as pure theory. But it is fun...

Lower bound. Observe that if the two rectangles are $x_1\times y_1$ and $x_2\times y_2$, then the rectangle $(x_1+x_2)\times(y_1+y_2)$ must have area larger than $P$. But then, the minimum perimeter rectangle of a given area is a square. This implies that $2(x_1+x_2+y_1+y_2) \geq 4\sqrt{P}$.