Throw an exception or return null

I guess what I'm asking is, is this the correct place to throw an exception?

If it were an exceptional situation, then yes. If the possibility of not finding anything that matches the criteria is expected then the situation is not exceptional and you should return null.

Yes, you should throw a RuntimeException to indicate an "exceptional" situation that should not have occurred. IllegalStateException probably fits the bill. Make sure to include a message with any information that will help you find the bug if it is ever thrown.

About your options, ask yourself if

1. Is it a good idea to have your program blow up at some point after this method returned an unexpected value (i.e. null)?
2. What exactly will be hidden if you mask out the null return value?
3. Is it a good idea to blow up immediately, just because there was a wrong value?

Personally I'd go for option 2 or 3, depending on whether I like the answer to question 2 or 3 better. Option 1 definitely is a bad idea, especially if it's not supposed to happen. If the program throws a NPE way after your function returned, you'll have a hard time figuring out where the null came from. Especially if it happens months after you finished working on this particular function.

If you choose to throw an exception, you immediately see where something went wrong and you can directly go there to figure out why it went wrong. Returning null and checking for it in the calling function could also work, but only if you don't fail silently, but actually do something to handle the problem properly.