To prove that a Feller process is strong Markov, it is not the continuity
of $P_tf(x)$ in $t$ that is important, rather the continuity in $x$. That is, we use that $P_t$ maps bounded continuous functions back into bounded continuous functions.
Here is a sketch of the usual proof: Let $T$ be $({\cal G}_{t})$-optional, and let $T_n$ be the standard dyadic approximations to $T$,
so that, each $T_n$ is $({\cal G}_t)$-optional and $T_n\downarrow T$ on $\{T<\infty\}$.
Fix $u\geq 0$ and $f\in C_b(E)$. Then, by the Markov property over $({\cal G}_t)$ we have
\begin{eqnarray*} \mathbb{E}(f(X_{u+T_n})1_{\{T<\infty\}})
&=&\sum_{k=1}^\infty \mathbb{E}(f(X_{u+k/2^n})1_{\{T_n=k/2^n\}})\\
&=&\sum_{k=1}^\infty \mathbb{E}(P_uf(X_{k/2^n})1_{\{T_n=k/2^n\}})\\[5pt]
&=& \mathbb{E}(P_uf(X_{T_n})1_{\{T<\infty\}}).
\end{eqnarray*}
Since $P_uf$ is a bounded continuous function, and $(X_t)$ has
right continuous paths, letting $n\to\infty$ gives
$$\mathbb{E}(f(X_{u+T})1_{\{T<\infty\}})= \mathbb{E}(P_uf(X_{T})1_{\{T<\infty\}}).$$
This shows that $(X_t)$ is a strong Markov process.
By way of contrast, consider the Markov process $(X_t)$ on $E=[0,\infty)$ that (starting at the origin) spends an
exponential amount of time at the origin, and then moves to the right deterministically at unit speed. It has transition kernel
$$p_t(x,A)=\cases{e^{-t}\delta_0(A)+\int_0^t e^{-z}\delta_{t-z}(A)\,dz&if $x=0$\cr
\delta_{t+x}(A)&if $x>0$.}$$
For a bounded, measurable $f$ on $E$ we have
$$p_tf(x)=\cases{e^{-t}f(0)+\int_0^t e^{-z} f(t-z)\,dz&if $x=0$\cr
f(t+x)&if $x>0$.}$$
Notice that even if $f$ is continuous, $p_tf(x)$ will typically have a
discontinuity at $x=0$ for $t>0$. The right hand limit is $\lim_{x\downarrow 0}p_tf(x)=f(t)$, while its value $p_tf(0)$ is a weighted average of $f$
over the interval $[0,t]$.
This process $(X_t)$ has continuous sample paths, is not Feller, nor is it strong Markov.
