Assume without loss of generality that the two squares to be removed are in different rows. (Otherwise turn the board 90°).
First cover the board in horizontal dominoes, and connect the two squares by a zig-zag line like this:
which follows the rule that if the line goes through one end of a domino, it immediately connects to another end. (The requirement that the two squares have different colors ensure that this will be true of the end of the path if only we start out in the right direction for this to hold at the beginning). Now you can flip dominoes along the zig-zag line to produce a covering that avoids the two squares.
With a bit of (easy) special-casing for the same-row case, this strategy can be extended to any size board as long as one of the side lengths is even and the other is $\ge 2$.
The variant can be settled by splitting up into three cases:
- $f_1(n)$, the number of ways to tile a rectangle ending with a flat line,
- $f_2(n)$, the number of ways to tile a rectangle where two corners meet in the middle,
- $g(n)$, the number of ways to tile a rectangle where the top right square is missing.
We have
$$
f_1(n) = f_1(n-1) + f_2(n-1) + 2 g(n-1)
$$
because the last tile of a rectangle ending in a flat line can either be an I tile or an L tile oriented in two ways. We just have
$$
f_2(n) = f_1(n-2)
$$
since the only way to create an $f_2$-type rectangle is to put down two horizontal dominoes at the end, and just as before, we have
$$
g(n) = f_1(n-2) + f_2(n-2) + g(n-1).
$$
From here, it's also possible to write down a linear recurrence for just the total $f(n) = f_1(n) + f_2(n)$ in terms of $f(n-1), f(n-2), \dots$. We have $f(n) = f_1(n) + f_2(n) = f_1(n) + f_1(n-2)$, so it's enough to solve for $f_1(n)$. In fact, as a linear combination of $f_1$ and its translate, $f$ will satisfy the same recurrence relation as $f_1$ with different initial conditions.
From $g(n) = f_1(n-2) + f_1(n-4) + g(n-1)$, we get the infinite series $g(n) = f_1(n-2) + f_1(n-3) + 2f_1(n-4) + 2f_1(n-5) + \dotsb$, and this gives us a recurrence
\begin{align}
f_1(n) &= f_1(n-1) + f_2(n-1) + 2g(n-1) \\
&= f_1(n-1) + f_1(n-3) + 2g(n-1) \\
&= f_1(n-1) + 3f_1(n-3) + 2f_1(n-4) + 4f_1(n-5) + 4f_1(n-6) + \dotsb \\
\end{align}
Subtracting $f_1(n-1)$ from $f_1(n)$, we get
$$
f_1(n) - f_1(n-1) = \color{red}{(f_1(n-1) + 3f_1(n-3) + 2f_1(n-4) + 4f_1(n-5) + 4f_1(n-6) + \dotsb )} - \color{blue}{(f_1(n-2) + 3f_1(n-4) + 2f_1(n-5) + 4f_1(n-6) + 4f_1(n-7) + \dotsb )}
$$
and most of the red terms cancel with blue terms, leaving us with
$$
f_1(n) - f_1(n-1) = f_1(n-1) - f_1(n-2) + 3f_1(n-3) - f_1(n-4) + 2f_1(n-5)
$$
or $f_1(n) = 2f_1(n-1) - f_1(n-2) + 3f_1(n-3) - f_1(n-4) + 2f_1(n-5)$. As observed earlier, this also means that the recurrence $$f(n) = 2f(n-1) - f(n-2) + 3f(n-3) - f(n-4) + 2f(n-5)$$ holds.
The first few nonzero terms of the sequence are $1, 1, 2, 5, 10, 22, 49, 105, 227, 494, 1071, \dots$, as computed by @PeterKagey in the comments and in the upcoming OEIS listing.
Best Answer
I will make frequent use of the words "domino" and "monomino" in this problem.
Let $a_k$ represent the number of ways to tile a $2\times k$ wall. We will seek to find a recurrence relation for $a_{k+1}$ by considering the rightmost between-column where there is a vertical line that doesn't cut through a domino.
Here will be the different summands of $a_{k+1}$:
So we have $$a_{k+1}=2a_k+3a_{k-1}+2a_{k-2}+...+a_1,\ a_0=1$$
This is A030186 in OEIS. Also note that, since $$a_k=2a_{k-1}+3a_{k-2}+2a_{k-3}+...+a_1$$ we can rearrange and add the two equations together to get
$$a_{k+1} = 3a_k + a_{k-1} - a_{k-2}$$ Either way, $a=(1,2,7,22,71,228,733,2356,\cdots)$, so $a_7=2356$.