Proof that a rectangle can't be tiled by XX XX:
One polyomino must end in a corner of the rectangle. So we have:

+--------
|AA AA
|

The gap can only be filled by a polyomino crossing in the other
direction.

+--------
|AABAA
|  B
|
|  B
|  B

Now, the gap in B can only be filled in two ways.  Both require a
polyomino
crossing parallel to A, but in different positions.  First consider:

+--------
|AABAA
|  B
| CC CC
|  B
|  B

Now, the gap between the second square of A and the first of C can only
be filled by a polyomino directly under and parallel to A.  This also
leaves only one way to fill the gap to the left of C:

+--------
|AABAA
|DDBDD
|ECC CC
|E B
|  B
|E
|E

Now, again there is only one way to fill the gap just below the first
square in C.  But adding this polyomino makes it impossible to fill the
gap in E:

+--------
|AABAA
|DDBDD
|ECC CC
|EFB
|*FB   * = impossible to fill
|E
|EF
| F

Now, consider the other position for C:
+--------
|AABAA
|  B
|  CC CC
|  B
|  B

The gap between A and C can only be filled by a polyomino parallel to
them,
but there are two possible places for it.  One pair of the x's in the
follwing figures must contain the other two D's:

+--------
|AABAA
|xxBDD xx
|  CC CC
|  B
|  B

Now, the gap in C can only be filled one way, and the gap thus created
between B and C can only be filled by another polyomino parallel to
them:

+--------
|AABAA
|xxBDD xx
|  CCECC
|  BFE
|  BF
|    E
|   FE
|   F

Now, the problem here is on the left edge.  If D extends to this edge,
then
the spaces below it can only be filled by placing two polyominos
vertically,
but this leaves a two-square gap at the left end of the fifth row which
cannot be filled:

+--------
|AABAA
|DDBDD
|GHCCECC
|GHBFE
|**BF
|GH  E
|GH FE
|   F

And otherwise, the same thing happens but the gap is in a different
place:
+--------
|AABAA
|GHBDD DD
|GHCCECC
|**BFE
|GHBF
|GH  E
|   FE
|   F