The serve would always learn the circuit you are using, so he would be able to tell which function you are evaluating over your data. There are methods to hide the function as well, but that feature is not provided by basic FHE.
Sure there are classes harder than NP, but it is necessary that our problems be in NP because otherwise it would be intractable for legitimate users. Take public key cryptography for example. The problem it is based on needs to be in NP because, given a ciphertext encrypted with one half of the key, you need to be able to efficiently verify (decrypt) it with the other half. If your encryption was in NEXP, but not in NP, it would take exponential time to decrypt even for users with the key. This is just one example, but I promise you that all our useful problems need to be in NP.
If our problems need to be in NP, then they also must not be in P. If P = NP, then it takes as long to verify a problem as it does to actually solve it. It would be just as fast to break an encryption as it is to decrypt with the key. A good explanation is in Impagliazzo's worlds. Interestingly, it necessary but not actually sufficient for P != NP. For instance, hard problems could exist but not trapdoor functions, which would make public key encryption impossible.
If you search and the search returns results, you are probably leaking because an observer can keep track of what sectors of the disk the results came from, and what bits passed through the registers of the CPU as it executed compare instructions, and use that to gain information about the data using statistical analysis.
A homomorphic search would not operate the way you are thinking. It would have to compute over the entire set of possible results (otherwise, as you say, the adversary learns at least that some results are not possible) and piece by piece obliviously combine them. As a simplification, if you know your search is going to only return one result then you can have the server run a circuit over each file which evaluates whether that file will be the result or not. If it is, out comes an encrypted one, if it is not then it will be an encrypted zero. The server then multiplies the file itself by this encrypted result and adds it to a running total. All the files which weren't chosen will be zeroed out and the single file you want will end up in this "register", although the server has no idea which one you wanted and which ones were zeroed out.
You do have the problem that anyone can come up with any valid ciphertext and jam it into your computation wherever they want, but we have some other cool stuff for verifying that only authenticated ciphertexts were used and that the function the guy evaluated was the one he was supposed to do. Lots of very cool stuff
Now, I can outline a cool use that you probably have not thought of which is a little different. Imagine that a server is storing some really sensitive stuff for me. Obviously I don't trust the server so I am encrypting all my files. If he is really sneaky, however, he can learn something about the contents of those files by watching when, where and how often I access them. We call this the access pattern, and usually people just write this off as a cost of doing business. However, with homomorphic encryption we can hide even that!
Since I can evaluate any program homomorphically over my data, I write a program that says "return file number x" and give it an encrypted value, say 50, for x. The server now evaluates this program, with my encrypted 50, over the entire set of files. What he gives back to me is my file that I wanted, but from his point of view he can't actually tell which file he gave me! All he knows is he ran a circuit over all the files in the database, with my input that specifies which one I want, but he can't tell what my input is because it is encrypted.