Does iterating $n \to 2n+1$ always eventually produce a prime number? Is it the case that for every non-negative integer $n$, iterating $n \to 2n+1$ eventually produces a prime number? (This is the same as asking whether for every positive integer $n$, there is a non-negative integer $k$ such that $2^k n  - 1$ is prime.) If this is not settled by proof, is there some heuristic argument either way?

(Following up on the connection to Riesel numbers mentioned in other answers ...)
For an infinite set of counterexamples, here is a proof-sketch (adapted from Baczkowski, et al.) showing that 
$$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73} \implies \forall k\in \mathbb{N}\  \big(f^k(n-1) \text{ is composite}\big),$$ where $f:\mathbb{N}\to\mathbb{Z}^+:n\mapsto 2n+1$ and $f^k$ is the $k$-fold iteration of $f$.  
Note that since $f^k(n-1) = n\cdot 2^k - 1$ for $n\in\mathbb{Z}^+$, the above is equivalent to
$$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73} \implies \forall k\in \mathbb{N}\  \big(n\cdot 2^k-1 \text{ is composite}\big),$$
which is to say that all such $n$ are Riesel numbers. 
The following congruence classes are sufficient for this purpose: 
$$\text{congruence classes for }k\text{ and }n\\
\begin{array}{|c|c|} 
k\equiv a_i\pmod{m_i} & n\equiv b_i\pmod{p_i} \\
\hline
0\pmod{2} & 1\pmod{3} \\
0\pmod{3} & 1\pmod{7} \\
1\pmod{4} & 3\pmod{5} \\
11\pmod{12} & 2\pmod{13} \\
7\pmod{36} & 4\pmod{73} \\
19\pmod{36} & 18\pmod{37} \\
31\pmod{36} & 13\pmod{19}
\end{array}
$$
As can be directly verified, the entries in the above table have the following properties:


*

*The congruence classes for $k$ form a covering system for the integers; i.e., every integer $k$ satisfies at least one of the congruences $k\equiv a_i\pmod{m_i}$. (To verify this, it is necessary to check only $k\in \{0,1,2,\dots,35 \}$, because $36$ is the least common multiple of the moduli $\{2,3,4,12,36\}$.)

*The congruences are such that in each row $i\ (1\le i\le 7)$, $b_i\cdot 2^{a_i} \equiv 2^{m_i} \equiv 1\pmod{p_i}$. Consequently, for all $i\ (1\le i\le 7)$
$$k\equiv a_i\pmod{m_i}\quad \& \quad n\equiv b_i\pmod{p_i}\\ \implies\ n\cdot2^k \equiv b_i\cdot 2^{a_i+r\cdot m_i} \equiv (b_i\cdot 2^{a_i})(2^{m_i})^r \equiv 1 \pmod{p_i}.$$ 
Now, by the Chinese Remainder Theorem, there exist simultaneous solutions to all seven of the congruences for $n$; in particular, the Extended Euclidean Algorithm yields the solutions 
$$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73}.$$
Therefore, for every such $n$, 
$$\forall k\in \mathbb{N}\  \big(n\cdot2^k-1\text{ has at least one divisor in the set }\{3,5,7,13,19,37,73  \}\big).\quad\quad\text{QED}$$
