Is there any monoid in which the product of two non-invertible elements could be invertible? I think the title speaks for itself. Thus I just explain the story behind the question. Of course, you may want to skip the story.
Story: Currently, I teach a course in linear algebra and matrices with a mathematician colleague of mine. In preparing for the class, we discussed together about one of the standard theorems of matrices saying the product of two invertible matrices is invertible. To understand the theorem and its converse, I naturally came to the question asked in the title. To my surprise, neither the colleague I discussed with, nor four other mathematician colleagues of mine could come up with an answer. But the question seems very natural and it is very surprising if it has been remained unnoticed. That is why I came to MO to find the answer.  
PS. None of the colleagues I asked the question is an expert in algebra, and I am a mathematics educator. 
PPS. You may replace "monoid" with whatever you wish, providing that you keep the rest of the title intact! Please keep your example natural (if there is one)!  
 A: The shift operator $S$ and its adjoint $S^*$ on $\ell^2(\mathbb{N})$ make another example. They are defined as follows: $$S(\delta_n):=\delta_{n+1}, \quad \forall n\in \mathbb{N}$$ and  $$S^*(\delta_{n+1}):=\delta_{n}, \quad \forall n\in \mathbb{N}$$ 
and $S^*(\delta_{1}):=0$, where $\delta_n$ is the characteristic function of the set $\{n\}$ and we extend $S$ and $S^*$ linearly. It is easy to see that $SS^*\neq id$, while $S^* S=id$. Therefore, they are not invertible, but $S^* S$ is invertible.  
A: Since the question came from an undergraduate level perspective, here's a slight variant on the answers given thus far that students might appreciate.
Take the vector space P of real polynomials.  There are two operators on P, D=differentiation and I=integration (to make integration a linear operator, we "set c=0"). Now DI is the identity map, but I is not onto (as the constant polynomials are not in its image) and D is not injective (as D(c) = 0 for any constant polynomial c).
A: There is exactly one monoid generated by two elements $p,q$ such that $pq=1$ but $qp\ne 1$. This is the bicyclic monoid $B$. In this monoid $p,q$ are not invertible while their product is 1 (hence invertible). Conversely, if a monoid contains $a,b$ such that $ab$ is invertible, then for some $c, abc=1$. If in addition $a$ is not invertible, then $bca\ne 1$. Hence $a, bc$ must  generate a copy of the bicyclic monoid $B$. Thus $B$ is the smallest counterexample to your question. 
A: Well, why not? 
Let $\oplus_{n \in \mathbb{N}} k$ be a direct sum of countably many copies of a 1-dimensional space over a field $k$; the direct sum affords a standard basis $e_i = (0, \ldots, 0, 1, 0, \ldots)$ with $1$ in the $i^{th}$ place. Define endomorphisms $A$, $B$ by $A(e_i) = e_{i-1}$ for $i \gt 1$, $A(e_1) = e_1$, and $B(e_i) = e_{i+1}$. I think you'll agree that $A B$ (first apply $B$, then apply $A$) is the identity, but $B A$ isn't invertible. 
