What is the intuition on why the longest path problem does not have optimal substructure?
The longest path problem does have optimal substructure, and this can be used to improve the trivial $O(n!)$ algorithm to an $\tilde{O}(2^n)$ algorithm. First we have to generalize the problem:


  Generalized longest path: Given a graph $G=(V,E)$, two vertices $s,t \in V$, and a set of vertices $A \subseteq V \setminus \{s,t\}$, find the longest path in $G$ from $s$ to $t$ avoiding the vertices in $A$.


Denoting the solution to this problem by $\ell(s,t,A)$ (the graph is understood), we have the recurrence
$$
\begin{align*}
&amp;\ell(s,t,A) = 1 + \max_{\substack{x \notin A \cup \{s\}: \\ (s,x) \in E}} \ell(x,t,A \cup \{s\}) \qquad (s \neq t), \\
&amp;\ell(t,t,A) = 0.
\end{align*}
$$ 
If the maximum in the first case is over the empty set (that is, if there is no path from $s$ to $t$ avoiding $A$), we assign $\ell(s,t,A) = -\infty$.

You can solve this recurrence using dynamic programming in time $\tilde{O}(2^n)$.

While there is optimal substructure here, there are too many parameters to keep track of, and this is what makes the problem intractable.