First, let us define some things:
- For simplicity, let's look always for boards where the width is equals to or larger than the height. If not, you can just rotate everything 90° to get one that is.
- Unsolvable board (UB) - One that no matter what you rotates, it is impossible to have all the dominoes with the same orientation.
- Smallest unsolvable dimension (SUD) - The smallest number possible as the dimension of an UB.
- Minimal unsolvable board (MUB) - An UB that has one of its dimension sized the SUD and the other dimension as smallest as possible for it being an UB.
- Impossible board (IB) - A board that can't be filled with dominoes. Like one that has an odd number of tiles.
Lemma 1. An UB exists if, and only if, a MUB exists.
If there is an UB (or a lot of them), there is at least one that is also a MUB. Trivially, if there is a MUB, so there is some UB because every MUB is also an UB.
This also means that if no MUB exist, so no UB exist either. If no UB exist, there can't be a MUB also.
Lemma 2. A solvable board that have both dimensions even can be solved with either orientation.
Proof: Solve the board with any orientation. Split it into many $2 \times 2$ subblocks and rotate all of them. The result is a board solved to the other orientation.
Lemma 3. A solvable board that have an odd dimension must be solved with the dominoes oriented along the other dimension.
Proof: By being odd, you can't fill it with dominoes that are even-sized along this dimension.
Lemma 4. A MUB can't be splitted in two rectangular subboards along either dimension.
Let's suppose we have a MUB that is splittable in subboards like this:
╔═══...═══╗ ╔═...═╦═...═╗
║ ║ ║ ║ ║
... ... ║ ║ ║
║ ║ ║ ║ ║
╠═══...═══╣ ... ... ...
║ ║ ║ ║ ║
... ... ║ ║ ║
║ ║ ║ ║ ║
╚═══...═══╝ ╚═...═╩═...═╝
If one of the subboards is unsolvable, then the big board was not a MUB. If any subboard is an IB, so is the big board, so it is not a MUB either. So, both subboards must be solvable.
However, if both subboards are solvable, then if solved in the same orientation, the great board would also be solvable, hence not a MUB.
So, we have that the solvable subboards must be solvable in different orientations. Considering lemma 2, one of them must have $odd \times even$ and the other $even \times odd$ dimensions. There is no way to divide the big board to have this result because the length in which it is divided can't be odd and even at the same time.
The conclusion is that a MUB can't be divided in two rectangular subboards in any way. This lead us to the following lemma:
Lemma 5. A MUB necessarily features for every pair of neighboring rows and every pair of neighboring columns, at least one domino spanning such a pair.
Because if it isn't, we will violate lemma 4.
Lemma 6. With one dimension sized 2, it is always solvable.
Proof: Let's start filling the top-left corner of the MUB with a SUD = 2. The two first possibilities are those:
╔═══╦═ ╔═╦═
╠═══╣ ... ║ ║ ...
╚═══╩═ ╚═╩═
By invoking lemma 4, those aren't MUBs. By invoking lemma 1, if there isn't a MUB, so there is not UB also. So, with dimension 2, it is always solvable.
Lemma 7. If there is a strip of dominoes where both sides have equally curved edges and it is not the entire board and the distance between the two curves is an even number of tiles, then it is not a MUB either.
Let's consider an area of a MUB like this:
═╦═══════╦══════
╚═╗ ╚═╗
A ╚═╗ B ╚═╗ C
... ╔═══╝ ╔═══╝ ...
║ ║
═╩═══════╩══════
Those curves contours dominoes. We see that the jagged line that divides $A$ from $B$ and $B$ from $C$ are equally curved. Further, we see that the distance between the curves are even. This means that we can delete $B$ and join $A$ and $C$. Thus $A+B+C$ is unsolvable if, and only if, $A+C$ is unsolvable. However, this implies that $A+B+C$ is not a MUB.
GAP: I still need to prove that by deleting $B$ does not allows any new rotations be possible by having $A$ join with $C$.
Lemma 8. If there is a strip of dominoes, even if not contiguous, where both sides have equally curved edges and it is not the entire board, then it is not a MUB either.
Roughly the same as lemma 7, but with uncontiguous areas:
═╦═══════╦═══════════════
╚═╗ ╚═╗
╚═╗ B1 ╚═╗ C
... ╚═══════╩═╦═══════╗ ...
A ║ B2 ║
═══════════════╩═══════╩═
We might delete both the areas $B1$ and $B2$ and fit $A$ into $C$.
Lemma 9. With one dimension sized 3, it is always solvable.
Proof: Let's start filling the top-left corner of a MUB with one dimension sized 3. The two first possibilities are those:
╔═══╦═ ╔═╦═╦═
╠═══╣ ... ║ ║ ║ ...
╠═══╣ ╠═╩═╣
╚═══╩═ ╚═══╩═
Considering lemma 4, this can't be a MUB.
Let us try this other configuration:
╔═╦═══╦═══
║ ╠═══╣ ...
╠═╩═╦═╩═╗
╚═══╩═══╩═
By removing the three tiles around the top-left one and fitting it in the hole that would result, we get a smaller board, meaning again that it was not a MUB. This is also an application of lemma 7.
Hence, there is no MUB with a dimension sized 3, so $SUD > 3$.
Lemma 10. With one dimension sized 4, it is always solvable.
Filling the left side of a MUB:
╔═╦═ ╔═══╦═ ╔═╦═╦═ ╔═══╦═ ╔═╦═══╦═ ╔═══╦═══ ╔═══╦═ ╔═══╦═══
║ ║ ╠═══╣ ║ ║ ║ ╠═══╣ ║ ╠═══╣ ╠═══╣ ╠═╦═╣ ╠═╦═╩═╗
╠═╣ ... ╠═══╣ ... ╠═╩═╣ ... ╠═╦═╣ ... ╠═╩═╦═╝ ... ╠═╦═╩═╗ ... ║ ║ ║ ... ║ ╠═══╣ ...
║ ║ ╠═══╣ ╠═══╣ ║ ║ ║ ╠═══╣ ║ ╠═══╣ ╠═╩═╣ ╠═╩═╦═╝
╚═╩═ ╚═══╩═ ╚═══╩═ ╚═╩═╩═ ╚═══╩═══ ╚═╩═══╩═ ╚═══╩═ ╚═══╩═══
A B C D E F G H
Well, $A$, $B$, $C$, $D$ and $G$ violates lemma 4, so they aren't MUBs. $E$, $F$ and $H$ violates lemma 7, so they aren't either.
Since there isn't a MUB with the smallest dimension as 4 and from lemmas 8 and 9, not with smaller sizes, then $SUD > 4$.
Lemma 11. If there is no two neighboring dominoes forming a $4 \times 1$ or $1 \times 4$ area alongside any of the four borders, it is not a MUB.
Let's try to fill the left side of an arbitrarily-lengthed side of the board (here it is 7):
╔═══╦═
╠═══╣
╠═╦═╝
║ ║
╠═╩═╗ ...
╠═╦═╝
║ ║
╚═╩═══
Whatever we do to fill up the spaces to the right of the vertically aligned dominoes, we will eventually violate either the lemmas 4 or 7.
So, any MUB must have at least two neighboring dominoes forming a $4 \times 1$ block. Since this is equally valid for all the borders, all the borders must follow this rule in order to a MUB be constructed.
Lemma 12. If there is no three neighboring dominoes forming a $6 \times 1$ or $1 \times 6$ area alongside any of the four borders, it is not a MUB.
From lemma 11, let's try to fill the left side of a MUB with a $4 \times 1$ block:
╔═══╦═
╠═══╣
╠═╦═╝
║ ║
╠═╣ ...
║ ║
╠═╩═╗
╚═══╩═
The only way to fill the gap without falling to the lemmas 4 or 7 is with this:
╔═══╦═
╠═══╣
╠═╦═╝
║ ╠═╗
╠═╣ ║ ...
║ ╠═╝
╠═╩═╗
╚═══╩═
Which we proceed with this:
╔═══╦═
╠═══╣
╠═╦═╩═╗
║ ╠═╦═╝
╠═╣ ║ ...
║ ╠═╩═╗
╠═╩═╦═╝
╚═══╩═
And whatever the way we fill the gap, we will violate lemma 7.
So, a $4 \times 1$ block isn't enough.
Lemma 13. It is always solvable.
Let's do an induction on lemma 12.
First, let's get a left side filled with a lot of vertical blocks without violating lemma 4:
╔═══╦═
╠═╦═╝
║ ║
╠═╣
║ ║
╠═╣
║ ║ ...
╠═╣
║ ║
╠═╣
║ ║
╠═╩═╗
╚═══╩═
Filling it in any way that follows the lines dividing the vertically oriented block will lead us to violate lemmas 4 and 7. So we will eventually build a pyramid:
╔═══╦═════════
╠═╦═╩═╗
║ ╠═╦═╩═╗
╠═╣ ╠═╦═╩═╗
║ ╠═╣ ╠═╦═╩═╗
╠═╣ ╠═╣ ╠═╦═╝
║ ╠═╣ ╠═╣ ║ ...
╠═╣ ╠═╣ ╠═╩═╗
║ ╠═╣ ╠═╩═╦═╝
╠═╣ ╠═╩═╦═╝
║ ╠═╩═╦═╝
╠═╩═╦═╝
╚═══╩═════════
And the lemma 7 will be violated whatever is the way we fill the top (actually to the right) of the pyramid.
Trying to not build a pyramid, would mean adding an horizontally-oriented domino somewhere in the middle. However, since the length of the previous layer of dominoes is always even, it means that at least two addition horizontally-oriented dominoes would be needed. Something like this:
╔═══╦═
╠═╦═╝
║ ║
╠═╣
║ ║
╠═╬═══╗
║ ╠═══╝ ...
╠═╣
║ ║
╠═╣
║ ║
╠═╩═╗
╚═══╩═
But this would just result in building a smaller pyramid in the even-sized gap or to fill it up nicely or any combination of that. In the odd-sized gap, we will need at least one other horizontally-oriented domino which will either leave another even-sized gap to build a pyramid or will subdivide it in two even-sized gaps which will see the same fate.
And what if the pyramid grows to reach the other side of the board before its top? In this case, it would leave two non-neighboring tiles to be filled with half-dominoes, and hence, impossible.
So, no $2k \times 1$ blocks along the border is enough to prevent lemmas 4 and 7 be violated. This means that either one will always be violated. Hence, it is impossible to build an UB, so there is no MUB either and all the possible boards are solvable.