You might like to check out
M. Reid, Klarner Systems and Tiling Boxes With Polyominoes, J. Combin. Theory A111 (2005)89-105.
and also
M. Reid, Asymptotically Optimal Box Packing Theorems, Elec. J. Combin. 15 (2008) #R78
These are motivated by the boxes in $\mathbb{Z}^n$ which can be tiled by a set of shapes. This informs some of the examples given, however the theory is just what you want.
For your particular problem of $6 \times 6,$ $10 \times 10,$ and $15 \times 15$ you can tile both a $30 \times 31$ (using one each of $30 \times w$ for $w=6,10,15$) and also a $31 \times 30.$ From your Theorem 3 it follows that all large enough rectangles can be tiled. LATER: From your corrected theorem $3$ one must add provided that the area is a multiple of $30.$
In the second article the author speculates that it may be much more difficult to generate the full list of tilable rectangles than results something like
"For an $m \times n$ rectangle to be tilable using the given basic rectangles, it is necessary that $14 \mid mn.$ Furthermore, there is a $C$ so that $14 \mid mn$ is sufficient provided that $m,n \gt C.$"
A final note: To simply read the desired dimensions $m,n$ of a rectangle takes $\log{m}+\log{n}=\log{mn}$ time (unless they are something like $m=2^{5^7}$) so it might be possible to improve your theorem $4$ to something like $\log{mn}+O(1).$ After some (huge but) fixed amount of work a criterion such as the above can be given (with an explicit $C$) and, if desired (increasing the huge preprocessing step manyfold), the "small" cases can be enumerated.
