What causes the error NotebookEvaluate::nbnfnd?

The problem is that FrontEnd related functions do not respect Kernel related settings.

I do not understand why this is not uniform. It is not clearly stated (I have not found it) which functions are FE related. Of course, it is easy to guess but that is not what you expect, the more that there is an appropriate tutorial which should explain that: NamingAndFindingFiles.

Ok, enough whining, I am talking about functions like:

NotebookSave NotebookOpen NotebookEvaluate NotebookImport

and the directory search stack for them is given by NotebookPath. So this should do:

PrependTo[
   CurrentValue[$FrontEndSession, "NotebookPath"],
   NotebookDirectory[]
]

NotebookOpen[nbFile]

In case anyone else stumbles across this problem: a possible workaround is given by the function AbsoluteFilename. Given a relative path it can construct the absolute one, which in return causes no problems for NotebookEvaluate.