Consider the hamiltonian path problem. As you mentioned, what we want to do is find out if there is or is not a hamiltonian path for some graph G'. I want to maybe take some liberties with this say say that, lets actually find the path here because returning yes/no doesnt really help us as we'd have to go verify in non-polynomial path. I think this liberty is ok though because if i can find hamiltonain path in polynomial-time, then still P = NP (http://en.wikipedia.org/wiki/FNP_(complexity)). So to find such path, I construct a random sequence guesser and set it loose. Sooner or later it will guess it, right? Why? Because the stars have aligned, so to speak, and bits on the memory chip formed themselves in such a way as to allow the random guesser happened to be successful. But what does it mean for the stars to aligns and cause bits on chip to be in that particular configuration? Surely, it wasnt magic. The environment affected the random number generator in a specific way, which is entirely predictable if we have very very detailed records of how things got to where they were. What I'm saying in my original post is that, realistically, you cannot treat a TM as "external" or "internal". You can in mathematics, but not in this real world we live in. That means, we have to treat everything that can possibly effect our deterministic TM as part of that TM's encoding, as it obviously effects how that TM works. So, if that's the case, since we see random sequence generators sometimes guess hamiltonian paths quickly, it seems our guesser TM (which is, in real life, nothing but an interface between us and the world around the TM) must be possible, but it will include in its encoding current state of the VISIBLE world around it. Which is fine, because its a large constant.
As far as the password, again, I'm taking some liberties here to get my point across. Some problem that's currently difficult to solve in polynomial time that will become solvable quickly if P=NP. I know I'm taking many liberties here.