The probability is
$$\frac{47058584898515020667750825872}{174165229296062536531664039375} \approx 27.0195\%$$
which matches the several simulations in your linked forum posts and in Paxinum's answer here.
First, I'll sketch a proof that the optimal strategy is to each time guess any rank (1 to 13) that has been seen the most number of times so far. If this is obvious to you, you can skip to the next section.
Optimal strategy
Let's call each guess you have to make a "round". So the game has at most 52 rounds.
Claim 1. The optimal strategy is to guess, in each round, a rank which maximises the probability of winning that round.
Proof. Essentially, a guess in any round does not constrain future guesses. Whatever you guess, it determines only whether the game ends immediately, and not the future state which is determined by what cards are in the deck and not by what you guess. Formally, suppose you have any strategy $S$ which in some round guesses a rank that is not optimal for that round. Then you can replace it with a strategy that in that round guesses the best rank, and in future rounds does exactly the same as $S$. (For this proof to work, we can modify the game so that we continue to make guesses for all 52 rounds, and only at the end decide that we have lost the game if we ever guessed a card correctly. This obviously doesn't affect the game.) This strategy has a strictly higher probability of winning than $S$; thus $S$ is not optimal.
Claim 2. In each round, the best guess is a rank which has been seen the most number of times.
Proof. Suppose rank $r$ has been seen $s_r$ times so far, and that there are still $D$ cards in the deck. So there are $(4-s_r)$ cards of rank $r$ still in the deck. If you guess $r$, the probability of losing that round, i.e., the probability that the next card that turns up has rank $r$, is $\frac{4-s_r}{D}$, which is minimised when $4-s_r$ is minimum, i.e., $s_r$ is maximum.
Putting them together,
Corollary. The optimal strategy is to guess, in each round, a rank which has been seen the most number of times.
Note that if you have seen multiple ranks the same number of times ($s_{r_1} = s_{r_2}$), it doesn't matter which one you guess. So let's assume wlog that you guess (say) the smallest such rank.
Computation
Now that we have fixed the strategy, how do we calculate the probability that it wins the game? In principle, we could try all permutations of the deck and see for how many it works. In practice, that leaves us with $52! > 10^{67}$ permutations, out of which you can at most sample a few and check (as the other answer and simulations have done), but you cannot possibly enumerate them all. Even if you notice that you don't care about the suit, you still have $52!/4!^{13} > 10^{49}$ orderings, and even if you observe that the ranks are symmetric you still have $52!/(4!^{13} \times 13!) > 10^{40}$ orderings to check.
For something better, notice that the state of the game at any point is captured by the number of times you have seen each rank so far (the $s_r$s above); the order in which they originally appeared is irrelevant now and in the future. Thus we can describe the state of the game by specifying $s_r$ for each $1 \le r \le 13$, and as $0 \le s_r \le 4$, this gives $5^{13} = 1220703125$, much more manageable. For something even better, note that as you don't care about the actual ranks but only their number, you can simply keep how many of the cards have been seen 0 times, how many have been seen 1 time, etc. That is, let $n_k$ denote the number of $r$ for which $s_r = k$. Then the state is $(n_0, n_1, n_2, n_3, n_4)$, and $\sum_{k=0}^{4} n_k = 13$. In fact, for any state in which $n_4 > 0$ you can determine the probability of winning from that state immediately (it is $1$, as you will keep guessing any $r$ for which $s_r = 4$, and never be wrong), so you only need to care about states in which $n_4 = 0$. The number of such states is the number of nonnegative integer solutions to $n_0 + n_1 + n_2 + n_3 = 13$ which is $\binom{16}{3} = 560$, a number small enough that with enough patience one could even handle it by hand.
Let $p_n$ be the probability of winning from state $n$, where the tuple $n = (n_0, n_1, n_2, n_3, n_4)$ is as above. The number of cards seen so far is $\sum_{k=0}^4 {kn_k}$. The number of cards still in the deck, $D$, is 52 minus this number. If $n_4 > 0$, then $p_n = 1$. Else, let $g$ be the largest $k$ for which $n_k > 0$. You will guess a rank counted in $n_g$. The number of ranks with each count, other than the one you guess, is
$$n'_k = \begin{cases}n_k & \text{if $k\neq g$,} \cr n_k - 1 & \text{if $k=g$.}\end{cases}$$
For a particular $k$, for each rank counted in $n_k$, the probability that the next card that turns up is of that rank is $\frac{4-k}{D}$, so the probability that some card of any such rank (other than the one we guess) turns up is $\frac{n'_k(4-k)}{D}$. Once such a card turns up, the next state has one less rank in $n_k$ and one more in $n_{k+1}$. That is, calling the new state $m = m(k)$,
$$m_j = \begin{cases}n_j - 1 & \text{if $j = k$,} \cr n_j + 1 & \text{if $j=k+1$} \cr n_j &\text{otherwise.} \end{cases}$$
So the probability of winning from state $n$ (if $n_4 = 0$) is
$$p_n = \sum_{k=0}^{3} \frac{n'_k(4-k)}{D}p_{m(k)}.$$
(The code, if anyone's interested, is at the end of the second revision of this answer).)
Edit: By Googling for the answer obtained above, I found this paper:
- Kevin Liwack, Oleg Pikhurko, Suporn Pongnumkul (2008), How to Play Dundee. arXiv 0803.0156
They consider this problem and obtain exactly the same answer. They too say "it seems that there is no general closed formula" and find the answer by computer; they seem to be using the algorithm I mentioned in passing above, which for this standard deck considers $5^{13}$ states. They also study the variant where the player has to specify all the sequence of guesses in advance. For some reason they have a relatively long proof that the greedy strategy above is optimal, but I can't find any bug in my proof above.
Let's look at a prefect game. In each turn, we will flip one of the cards and after we've seen it, we will flip the other one, so the second (fourth, sixth...) choice of cards depend on the choice of the first (third, fifth...) card.
Since there is 1 in 39 cards to complete the pair once we've selected the first card, there is a chance of $\frac{1}{39}$ of pairing the first two cards.
Once that is done, we are left with 38 cards, so if we flip one up, there is a chance of $\frac{1}{37}$ to complete the secong pair.
...
Once we arrive to the last pair of cards, if we flip one of them up, there will be just one remaining card so the chance of completeing the last pair is $\frac{1}{1}$.
So the chance of a perfect game is:
$$\prod_{k=1}^{20}\frac{1}{2k-1} = \frac{1}{319830986772877770815625} \simeq 3.12ยท10^{-24}$$
Best Answer
For $n=2$ there is a better strategy. Flip two cards. If they match ($p=\frac 13$) you are done in two turns. If they don't match, flip one old and one new card. The improvement comes because these might match and if not, you know where all the cards are and are done in four turns. Now you have $\frac 13$ chance of being done in three turns, for an average of $3$. This carries over to longer games. Clearly the last turn in the discovery phase you should turn one of the unmatched old cards and one new card. You will match with probability $\frac 12$. If there are no unmatched old cards, turn the two new ones and they will match.
You can write a recurrence. Define $N(n,k)$ as the expected number of flips to deal with $n$ pairs when you know the locations of $k$ unmatched cards. From each flip you have the outcomes: they match, neither matches a known card, one matches a known card, both match known cards. I believe the best strategy is to flip two unkowns until there are only two, then flip one unknown and one known.