Respuesta: sí. Se puede garantizar el acierto enumerando todas las trayectorias posibles.
Cada trayectoria queda determinada por dos enteros:
$$
(X,V),
$$
donde $X$ es la posición inicial y $V$ la velocidad constante. Si conocemos ese par, sabemos dónde está el submarino en cualquier día $t$:
$$
X+tV.
$$
El problema es que no sabemos cuál es el par real. Pero los pares de enteros pueden ponerse en una lista infinita:
$$
(x_0,v_0),(x_1,v_1),(x_2,v_2),\ldots
$$
Una forma concreta de hacerlo es recorrer la cuadrícula $\mathbb{Z}\times\mathbb{Z}$ por diagonales, como en la enumeración de Cantor. El orden exacto no importa; lo importante es que todo par de enteros aparezca alguna vez.
La estrategia es esta: en el día $t$, tomas el par número $t$ de la lista, $(x_t,v_t)$, y disparas a la posición donde estaría el submarino ese día si su trayectoria fuera esa:
$$
x_t+t v_t.
$$
Ahora considera el submarino real. Tiene algún par fijo:
$$
(X,V).
$$
Como la lista contiene todos los pares de enteros, ese par aparecerá en una posición finita de la lista. Supongamos que aparece en la posición $k$:
$$
(X,V)=(x_k,v_k).
$$
Entonces, en el día $k$, la estrategia dispara a:
$$
x_k+k v_k.
$$
Pero como $(x_k,v_k)$ es precisamente el par real, esa posición es:
$$
X+kV.
$$
Es decir, la posición exacta del submarino en el día $k$. Por tanto, ese día el disparo acierta.
No sabes de antemano cuándo ocurrirá, porque no sabes en qué lugar de la lista está el par real. Pero si se fija una enumeración concreta de $\mathbb{Z}\times\mathbb{Z}$, el día de acierto queda determinado por la posición que ocupe en esa lista el par real $(X,V)$.
Lo esencial es que esa posición existe y es finita.