You might like to check out 

 *M. Reid*, [Klarner Systems and Tiling Boxes With Polyominoes][1], J. Combin. Theory A111 (2005)89-105.

and also

*M. Reid*, [Asymptotically Optimal Box Packing Theorems][2], 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.




  [1]: http://www.sciencedirect.com/science/article/pii/S0097316504001761
  [2]: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r78/0