This is a to long for a comment:
Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains a Hamiltonian path. (And the analogues question for a cycle if and only if $G$ contains a Hamiltonian cycle).
Let $m(N)$ be the smallest $n$ such that $G(n,N)$ contains a Hamiltonian path and $m_c(N)$ the smallest $n$ such that $G(n,N)$ contains a Hamiltonian cycle.
From a some calculations with sage one can see that $$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&437\\4&?(\geq9254)&9641 \\5&?&?(\geq490463)\end{array} $$ Example for $15$, $32$ and $305$ are already in your question, I calculated examples of the 473 and the 9641.
For the entries with questions marks: these are just some guesses. For $m(4)$, one can quickly see, with the help of sage that $G(9253,4)$ does not have a Hamiltonian path, and neither $G(n,4)$ for $n=9252, 9251, 9250,\dots$ or $9210$. But so far I could not find a Hamiltonian path in $G(9253,4)$, maybe somebody else can give it a try. Similarly, $G(490462,5)$ does not contain a Hamiltonian cycle.
I find the argument in your "Additional Information" quite convincing and would expect that most graphs with more than $m(N)$ (or $m_c(N)$) satisfy your condition; with possibly a few exceptions just above $m(N)$ (or $m_c(N)$). Maybe a probabilistic argument could turn this into a proof.
One could also ask about the asymptotics of $m(N)$ and $m_c(N)$ or find lower bounds for them.