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][1] one can see that 
$$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&473\\4&?(\geq9254)&9641
\\5&?&?(\geq490463)\end{array} $$
Example for  $15$, $32$ and $305$ are already in your question, I calculated examples of the [473][2] and the [9641][3]. 

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.

----------
**Update:** By request from martin, here is the [sage][1] code for it. For N=3, n=473 it takes .2 seconds to find the hamiltonian cycle, for N=4, n=9641 it takes 290 seconds on my computer.

    def getgraph(n,N,path):
        powers=[(i+1)^N for i in range(ceil((2*n)^(1/N)))]
        G=Graph()
        G.add_vertices([1,..,n])
        edges=[]
        for p in powers:
            for i in range(1,ceil(p/2)+1):
                if i<=n and p-i<=n and p-i>0:
                    edges.append([i,p-i])

        if path:   #add an extra vertex connected to all others
            G.add_vertex(0)  #to get path from cycle
            for i in [1,..,n]:
                edges.append([0,i])
        G.add_edges(edges)
        return G

    path=False
    n=473
    N=3
    time G=getgraph(n,N,path)
    time hami=G.hamiltonian_cycle()

    l=hami.cycle_basis()[0]
    print [l[(i+l.index(int(not(path))))%len(l)] for i in range(len(l))]
    

    

  [1]: http://sagemath.org/
  [2]: http://page.mi.fu-berlin.de/moritz/mo/power/473.txt
  [3]: http://page.mi.fu-berlin.de/moritz/mo/power/9641.txt