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.

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