My deck has two Maesters, let's say one copy of Grand Maester Pycelle and one copy of Maester Cressen. Am I correct in assuming that if I have both in hand and I play the plot Here to Serve, I cannot play either of them with the Plot's action?

Here to Serve allows you to search your deck for a Maester. Your hand is not a part of your deck, so no, you cannot put into play a card from your hand with Here to Serve.

Hopefully, you would find a copy of one of those cards, put it into play using the plot, then play a duplicate on it during the Marshalling Phase.

Oops! Missed that you only had one of each (no copies).

In fact are you even able to search your deck with the knowledge that there is neither left remaining in this situation? Perhaps if you wanted to reshuffle because you have just been served a "The Bear and Maiden Fair" and you know you won't like what's coming as a quick example.

I know this has been the case for another Fantasy Flight LCG in Netrunner and sort of sends a tell to your opponent, but nonetheless remember this being a corner case if it comes up.

You are forced to search your deck (and shuffle it). The card ability initated, and its effect must be carried out. You are not, however, forced to find the object of your search (this is explicitly stated in the rules, largely to avoid having to call a TO every time someone fails to ensure they're not cheating).