Two plaintexts map to the same ciphertext in fully homomorphic encryption?
Same ciphertext from different keys

Since deterministic Homomorphic encryption schemes are insecure, all the proposed HE schemes randomize the ciphertexts in some way, i.e., during the encryption, some random value $r$ is sampled and combined with the ciphertext.

Hence, given two different keys $k_1$ and $k_2$ and two messages $m_1$ and $m_2$, we usually can find two possible random values $r_1$ and $r_2$ that make $Enc(m_1, k_1; r_1) = Enc(m_2, k_2; r_2)$, therefore, the answer for your question is yes.

For example, in schemes based on the Approximate-GCD problem, such as DGHV10, a message $m_i$ is encrypted as $pq_i + r_i + m_i$, where $p \in \mathbb{Z}$ is the secret key and $q_i$ and $r_i$ are random integers.

So, given two keys $p_1$ and $p_2$ and two messages $m_1$ and $m_2$, it is sufficient to take $q_1 = p_2k$, $q_2 = p_1k$ (for any $k$) and $r_1 = r_2 + m_2 - m_1$.

Then we see that 
$$Enc(m_1, p_1; q_1, r_1) = p_1q_1 + r_1 + m_1 = p_1p_2k + r_2 + m_2 = p_2q_2 + r_2 + m_2$$
which corresponds to $Enc(m_2, p_2; q_2, r_2)$.

For the BGV scheme, it is a bit more complicated, but you can still choose keys such that it holds. Namely, let $s_1, s_2 \in R := \mathbb{Z}[x]/\langle f(x) \rangle$ be two secret keys and use the same $\vec e$ in the corresponding public keys. Than, we can set

$$m_1 + s_1\langle \vec a, \vec r \rangle + 2\langle \vec e, \vec r \rangle = m_2 + s_2\langle \vec a, \vec r \rangle + 2\langle \vec e, \vec r \rangle \mod q$$
where $\langle \vec a, \vec r \rangle $ denotes the inner-product and it is a polynomial in $R$.

This equality is satisfied if $s_1 = m_2\langle \vec a, \vec r \rangle^{-1} + s_2 \mod q$.

Computational "paradox"

First of all, you are not modeling the running times correctly, because finding four keys that produce the same ciphertext is more than two times slower than finding two keys, that is, you cannot simply use $T(key)\cdot|X|$, you should use $T(key, n)$ and $T$ is most probably not linear in $n$, since you have to solve systems with more than $n$ variables to find the keys.

Furthermore, that apparent contradiction with the "laws" of computation is not implied by the ability of finding such keys. Actually, what you need is not only to create equal ciphertexts but also two find a way that their evaluation yield the same ciphertext. It might be the case that $c_1 := Enc(x_1, k_1) = c_2 := Enc(x_2, k_2)$, but $Eval_1(f, c_1) \not = Eval_2(f, c_2)$, and therefore, you could not evaluate $f$ homomorphically a single time and decrypt it with two different keys.