It is true! An even polyomino with one hole is tileable by dominoes.
The proof below has a few sketchy elements; a proof without those will be nice.
Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).
Here, tileable means tileable by dominoes.
A ring is a polyomino where each cell has exactly two borders. All rings are tileable.
A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.
An example of this manipulation:
- A $2 \times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.
An example of this manipulation:
- All convex corners of a even polyomino are one of these four types:
(This part is a bit sketchy; it requires considering many cases.)
- If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:
- A figure with only type 3 and 4 convex corners and one hole cannot contain a $2\times2$ subfigure.
Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2\times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2\times 2$ subfigure.
In this^ image, there is a $2 \times 2$ square, contained in a $3\times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.
- We cannot have any X or T junctions in a figure with no $2\times2$ subfigures, no peaks, and one hole.
Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.
Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.
- This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).
(This is also sketchy, and require cases to make sure we cannot have other possibilities.)
- This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2\times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.
Some remarks:
- The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2\times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)
- An algorithm follows immediately from the border manipulations.
If I understand your definitions right and if you'll forgive the crude MSPaint diagram, I think this example shows that such a polyomino can be nontileable. Here the orange line traces out the strip for $R$, the pink line traces it for $S$, and the light/dark gray squares are the squares remaining in $R-S$, which are clearly non-tileable.
Edit: on second thought, a simpler example can be found in the 3x3 square, where $S$ is again traced out by the pink line:
Best Answer
After thinking about it all day I discovered a trivial proof.
First note that any figure with all sides even and no holes can be tiled with dominoes so that they are all horizontal, and that each domino shares its long edge with at most one other domino.
Now take any figures with all sides even, possibly with holes (whose sides must also be all even). First tile it as if it had no holes. Then remove all dominoes that lie completely inside a hole. Some dominoes may cross the border of the hole. These dominoes must occur in pairs (since the hole sides have even length), so each pair that overlaps a hole border can be replaced with a single domino outside the hole. The tiling is complete.
Below is the procedure on the figure above.
The proof also works if the outer border has only all horizontal sides of even length and all holes have their vertical sides even length.
Update: The proof also works for figures with sides divisible by $n$ and bars of length $n$ instead of dominoes if the holes are at least $n - 1$ units apart. I think (but am not sure) that we can remove this constraint if the tile set is all $n$-ominoes.