Support for ruling that the monk does recover from exhaustion.
I immediately think of these things in the large scale:
While there's ambiguity with creatures that get this ability ("This ability" referring to the mechanic of not needing to eat/drink, not specifically the Monk's "Timeless Body".) while still being able to eat/drink, you would also give this ability to a creature who thematically can't eat/drink, to mechanically denote the fact that they don't need to.
If the ability didn't allow the creature to recover exhaustion, any creature that doesn't (through regular means, or at all) eat or drink because they can't (Assuming they can still become exhausted, which is most creatures anyway) would be mechanically in the territory that if they go for a swift jog, they may as well keel over dead, because they physically can't rest it off.
Having large swathes of creature types be capable of simply dropping dead if they go for a brisk enough walk, let alone the arbitrary inability for their bodies to not be able to recover from moderate stress when they thematically should, is broken mechanics.
With the above considered, a creature that can't obtain sustenance from food is intrinsically capable of resting without eating. Of course it gets a bit blurrier when you have a creature type that can physically ingest food, and can, you know, taste things, drink a healing potion, and feel happy when they eat their mother's home-cooked pie, and generally possesses the appropriate biological faculties to do so, but doesn't rely on consuming things for continued survival.
Consider playability and Rules as Intended
I would say, though, that you can (and should), after discussion with players, say it works any particular way you like when getting the ability; and so for the sake of answering this question, I should do so in an 'attempting to define the official intent' way. In that sense, saying that the mechanic "This does not need to eat or drink" means that you do not need to eat or drink to do things that mechanically require you to do so, as I believe is required for the mechanics to make sense uniformly, including things that are except from eating under any circumstances, but to specifically say that "... however, if you can eat or drink, you need to eat and drink when you're mechanically required to, even if you don't need to eat or drink to survive."
It's thematically weird, and hurts verisimilitude, that you supposedly don't need food or water, yet you don't have even the basic level of sustenance required for your body to recover from having been out in the desert, or marching for a day. That doesn't really seem like 'not needing food', feels more like "I can't quite die from lack of food, but I sure can starve to the point of being incapacitated, physically incapable of getting up, and I'm too weak to recover no matter how long I spend.". That's by definition starving, (or dying of thirst), so at that point you may as well formally rule that Timeless Body just prevents you from straight-up dying of lack of sustenance, but not from having the lesser effects of it, because after all, aside from it's temperature and stress related functionality, Exhaustion is D&D's main way of mechanically simulating hunger - if you become unable to physically recover from Exhaustion because you can't eat, you are by definition suffering the effects of starvation.
Apply the Rule of Cool
That's that ability's special thing, why would you heap technicality and "but if you turn to page 137's text" on top of it? Depending on the DM and party's style, hunger is usually very abstracted in D&D, aside from special 'the party becomes trapped without food, thus learning of the value they've been taking for granted the whole time' (which sounds familiar). Since you're asking about how this should be ruled, I assume you've not dealt with it in the past, and so this is the first time that the monk is even getting to use the ability (they may not even realise they can go without food, if it's been a while since they've gotten it).
Why would you, in a situation where the ability to go without food, the character's special thing, can actually be useful, consider saying "... but actually no, because page {number} contradicts the mechanics statement on page {other number}. I think the designers of D&D intended that your new level 15 monk who is strong enough to sustain themselves with their very soul would starve if they ran out of food, and I think that is absolutely correct and we can't go against it. :) "
While I can't know what your intent with "have a party gain a level of exhaustion" is, I can only assume your plan to create an amazing game and story won't somehow be ruined by the fact that the players realise someone who has a niche thing that had never been useful before which suddenly becomes a really valuable tool that doesn't solve the situation, but allows them to get a minor spotlight in the situation. The fact that they can do that will be kept more in mind for future player strategizing, while making the character more memorable in the process. (In a natural way, that usually comes to every character in some form over the course of play.)
I think mechanically, thematically, and in a meta sense, not needing food means you don't need food.
But of course, if it makes the most sense between you and the players that the character in question is still weakened by lacking external sustenance, by all means. The book is only there to facilitate play, not to dictate what you can and can't do. Just don't decide it yourself and throw it at them, lest the player be let down not getting what they'd think the ability says they should, and because if these characters are in a long term campaign, you're making an equally long term decision about a major aspect of the character (even if it doesn't show up all that often) that can affect many future encounters you can't foresee, and you shouldn't just decide by yourself on a whim something that'll affect not just this, but potential future encounters, especially when it has to do with one of the characters, as opposed to external influence.
