How long is too long to wait for a rejection because of a lack of reviewers?
If anything, my reaction is that two months is too soon to absolutely give up on trying to find an appropriate referee.  Generally (at least in my discipline) people are given a week or two to accept or decline a referee request, so two months probably means that not more than ten or so people were asked.

My understanding of what it means to be an editor is that they should in principle be working harder to find a suitable referee.  However, if the editor is having an especially bad time of it, it may be worth letting the author know: maybe they will choose to resubmit to a different journal or to switch to a different editor at the same journal.  The latter happened to me years ago: the editor that I submitted to asked one person to referee, got referred to a second, and so forth.  He reported failure to me after the loop closed up.  But the failure was conditional failure, and he gave me the option of switching to a different editor at the same journal, which I did.  (Unfortunately after that the paper still was not treated well, but that's not part of the present story.)

Academia is specialized, but it's not that specialized: probably most journal submissions have at least 100 suitable referees in the world, right?  If so, then two months is way too soon to say definitively that a suitable referee could not be found.  In my experience, editors often "sugarcoat" the things that they tell authors -- probably because they didn't like the hate mail they got from their earlier, more forthright approach -- to the extent that if you take literally the reasons given for objection, they often sound rather silly.  In this case I might suspect that "I spent two months and I couldn't find a suitable referee" is meant to be code for "I asked enough people whose opinions I trusted, and while they were not willing to formally referee the paper, they told me that it did not interest them and thus probably did not merit publication."  If the editor is himself making a judgment call about the suitability of the submission, in my opinion that's fine but they should be upfront about it.  

Unfortunately the current culture of academic journals makes extracting "the real story" from the editor almost prohibitively difficult.  In practice it is probably in your poster's best interest just to try again at a different journal.