It is a very nice question!

But I claim, unfortunately, that the tiling problem for your special kind of tile sets
is also undecidable. Specifically, I claim that the ordinary Wang
tiling problem reduces to an instance of your kind of tiling
problem. That is, if we are given a finite list of ordinary Wang
tiles $w_0,\ldots, w_n$, then we can create (according to a
computable procedure I shall presently explain) a new set of tiles
$t_0,\ldots,t_k$, such that the original set of tiles admits a
tiling if and only if the new set admits a tiling, and furthermore
the new set of tiles $t_i$ obey your deterministic property.

The new tiles are obtained from the previous tiles by annotating
the labels on the original tiles. Given any Wang tile $w$, labeled
with $1$ and $2$ on the left and right side, respectively,

```
-------------
| 3 |
| |
w = |1 2|
| |
| 4 |
-------------
```

and for each tile $u$ with a label of $1$ on the right (so that it
could legitimately form $uw$), we create a tile $t_{u,w}$ labeled
by $(u,1)$, $(w,2)$ on left and right, respectively, and otherwise
the same as $w$ on top and bottom. That is, we think of $(u,1)$ and $(w,2)$ as individual new colors in the new tile set.

```
-------------
| 3 |
|u w|
t_{u,w} = |1 2|
| |
| 4 |
-------------
```

The meaning of the annotation is that the right-hand side label
$(w,2)$ indicates $w$ and therefore contains all the information needed to know the top and
bottom labels, and we add $(u,1)$ on the left simply so that it
can match the corresponding new tiles corresponding to some $u$
that could match with $w$.

Thus, if $uw$ can be extended to a sequence $ruw$ in the original
tiling, then $t_{r,u}t_{u,w}$ is legitimate in the new tiling. So
any tiling of the plane using the original tiles can be
transformed into a tiling using the new tiles. Conversely, if
$t_{r,u}t_{u',w}$ is legitimate in the new tiling, then it must be
that $u=u'$ becase the annotated labels match, and furthermore $uw$ is
legitimate in the original
tiling, since we only made $t_{u,w}$ when $uw$ was legitimate. So every tiling with the new tiles immediately produces a
tiling using the old tiles. (Indeed, the tilings themselves are
computable from one another.)

Finally, the new tiles obey your deterministic property, because
the annotations on the side labels contain all the information
necessary to determine the top and bottom labels. Indeed, the right color alone determines the top and bottom colors on these tiles, and severely restricts the possible left colors as well.