Age and residual life time of the Poisson process Original Question
Let $N(t)$ be a Poisson process with intensity $\lambda$. Let $T_1<T_2<...$ be the occurrence times. Let $T_0=0$. For any $t>0$, define the $age$ random variable to be
$A_t := t-T_{N(t)} $
the $residual$ $life$ $time$ random variable to be
$R_t:=T_{N(t)+1}-t$
In other words, $age$ is the time elapsed since the last occurrence and $residual$ $life$ $time$ is the time remaining until the next occurrence.
Using a similar logic to the first answer of Relationship between poisson and exponential distribution, one can show that $A_t\sim$ Exp($\lambda$). Below is the reproduction of the logic:
$A_t>a \Leftrightarrow T_{N(t)}<T_{N(t)}+a<t \Leftrightarrow N(T_{N(t)})=N(T_{N(t)}+a)=N(t)$
I understand that the second $\Leftarrow$ logic requires the last equation to ALWAYS hold. 
Continue on with user28's proof
$P(A_t>a)=P[N(T_{N(t)}+a)-N(T_{N(t)})=0]=P[N(a)=0]=e^{-\lambda a}$ 
However if I admit that $A_t\sim$ Exp($\lambda$), I will quickly run into the following paradox:
Since the exponential distribution is memoryless, one can easily prove that $R_t\sim$ Exp($\lambda$) and is independent of $A_t$. This means that two independent Exp($\lambda$) exponential random variables $A_t$ and $R_t$ sum to a different Exp($\lambda$) exponential random variable -- the interarrival time of the Poisson process.
According to Wikipedia https://en.wikipedia.org/wiki/Exponential_distribution, the sum, however, should be Gamma(2,$\lambda$) (in the ($\alpha,\beta$) parameterization).
What did I do wrong here?
Was I too ambitious claiming $T_{N(t)}<T_{N(t)}+a<t \Leftrightarrow N(T_{N(t)})=N(T_{N(t)}+a)=N(t)$
? 
If the $\Leftarrow$ can not be claimed, then I can only get $P(A_t>a)>e^{-\lambda a}$. How should I get the distribution for $A_t$ in this case?

First Edit
I take the Poisson process as a limiting process of the Bernoulli process and arrive at the same conclusion $A_t\sim$ Exp($\lambda$). The key steps are as follows:
Step 1: Review the Law of Small Numbers for Bernoulli processes
 
Step 2: Let $t\in\mathbb{N}$ for the Bernoulli process $\{X_r^m\}_{r\in\mathbb{N}/m}$. Then by time $t$, there are a total of $mt$ trials, and $N^m(t)$ of them are successes. For $N^m(t)>0$, the time that the last success takes place, $T_{N^m(t)}$, takes any value between $\frac{1}{m},\frac{2}{m},...,t$. Let $k\in\mathbb{N}$ such that $0<k<mt$  
$P(t-T_{N^m(t)}=\frac{k}{m})$
$=P($ the last $k+1$ trials of the total $mt$ trials are one success and $k$ failures $)$
$=p_m(1-p_m)^k$
When $k=mt$, $P(t-T_{N^m(t)}=\frac{k}{m})=$$P($ all $mt$ trials are failures $)=(1-p_m)^{mt}$
Therefore
\begin{split}
P \Big(t-T_{N^m(t)}>\frac{k}{m} \Big) &= \sum_{i=k+1}^{mt-1}P\Big(t-T_{N^m(t)}=\frac{i}{m}\Big) + P\Big(t-T_{N^m(t)}=\frac{mt}{m}\Big) \\
& = p_m(1-p_m)^{k+1} + ... + p_m(1-p_m)^{mt-1} + (1-p_m)^{mt} \\
& = (1-p_m)^{k+1}
\end{split}
Taking $x=\frac{k}{m}$ and the limit $\lim_{m\to\infty} mp_m = \lambda$ yields
\begin{split}
P (t-T_{N^m(t)}>x) = \Big(1-\frac{\lambda}{m}\Big)^{mx+1} \to e^{-\lambda x}
\end{split}
This again leads to the conclusion that $A_t\sim$ Exp($\lambda$) and the same paradox in the original question. 
 A: Yes you are correct in suspecting that here the if and only if condition does not hold i.e.,
$A_t>a  \Rightarrow N(T_{N(t)})=N(T_{N(t)}+a)=N(t)$ holds but not the other way around. 
This can be seen as follows. Take $a$ such that $t<T_{N(t)}+a<T_{N(t)+1}.$ Then we still have the event $N(T_{N(t)})=N(T_{N(t)}+a)=N(t),$ but now $A_t<a.$

Edit 1:
An attempt:
Let $X_t = T_{N(t)+1}-T_{N(t)}.$ We know $X_t \sim Exp(\lambda).$ Also from the memoryless property of exponential distribution $R_t \sim Exp(\lambda).$ However we know
$$
A_t = X_t - R_t
$$ 
Using chain rule of probability.
\begin{eqnarray*}
P(A_t>a)&=& P(X_t-R_t>a)=\int_a^\infty P(R_t<x_t-a|X_t=x_t) dP(X_t = x_t)\\
&=& \int_a^\infty P(R_t<x_t-a|X_t=x_t) \lambda e^{-\lambda x_t} dx_t
\end{eqnarray*}
Till this step we do not require any dependence condition. Now we need to figure out the distribution $P(R_t<x_t-a|X_t=x_t)$ since $X_t,R_t$ are not independent.

Edit 2: I think I understand the basic problem, but still need to think a bit more. The following statement is true, "Consider a poisson process on a line, then randomly choose a point in the line. Then the distribution of the time to both the next and previous arrival point will be $Exp(\lambda)$, i.e. the process looks poisson in both direction." This is called the "Hitchhiker's paradox". But actually this is not a paradox, and can be proven, because we are inherently conditioning on the fact that we randomly arrive at a point $T_{N(t)}<t<T_{N(t)+1},$ and the probability of arriving at a larger interval is more than arriving at a smaller interval. So we observe a distance biased distribution. Its slightly non-intuitive. I suspect a similar thing happening here.
