(thanks to michael kleber for reviving this.)
I just looked at Gosper's pix of tilings of rectangles by 1x3s. All seem to have at least one substructure of 3x3 as three 1x3s. Are there tilings without this substructure?
check out "tiling a polygon with rectangles" by claire and richard kenyon, proceedings of the 33rd foundations of computer science (FOCS), 1992, pp. 610-619. theorem 3 of that paper asserts that, given a simply connected polyomino region tiled by m x 1 (vertical) polyominoes and 1 x n (horizontal) polyominoes, then any two such tilings can be obtained from one another by steps of the form replace an m x n subrectangle tiled by horizontal tiles by one tiled by vertical tiles or the inverse operation. this easily implies that the answer to rich's question is "no". mike