There's nothing in any of the manuals or cluebook for the game that mentions or hints that mandrake needs to be found at new moons, and no in-game character tells you either.

U4 has been one of my very favorite games since I first played it on the C64 decades ago, but this is one of the very few game secrets that Origin messed up on. I can imagine a lot of people getting frustrated looking for it. Especially since no one gives you the exact location either, plus the hazard of getting all your characters poisoned while searching. They should have dropped the moons requirement.

The only counter-argument I can think of would be that you don't absolutely need any of the spells that use mandrake, but they are almost all very useful.

The second of these sentences is not true; you can enter the Abyss with a smaller party, but you'll be kicked out at the very end before the final quiz (but after the last combat challenge). Actually, Magic Wand > Magic Axe here. (This means that, if you ignore spellcasting ability, the two magic-oriented classes are two of the three best classes in the long run.)

Also, in the Abyss, non-magical weapons will never hit.

(The NES version differs a bit in that non-magical weapons work fine in the Abyss. However, the Magic Bow has one advantage that the axe and wand don't; you can equip a bow and a melee weapon at the same time (so you can get high melee damage while also getting ranged attacks), but can't do the same with the axe or wand. Then again, the Abyss's party requirement is completely different; it doesn't matter how many companions you've recruited (and level 7 is enough to recruit them all on NES), and you end up going through the Abyss solo.)

(Considering computer versions, not NES, where power valuse are different, though the ordering doesn't change if you don't compare melee to ranged weapons.)

Actually, I believe the Magic Axe has only 96 power, not 156, while the Magic Wand is 160. Also, keep in mind that Strength is added to your weapon's attack power, so such power differences are less significant.

Anyway, the price difference makes more sense in the NES version, where the +2 Sword (Magic Sword) is stronger than the +1 Axe (Magic Axe), but the two can't be equipped at the same time, whereas the +1 Bow *can* be equipped alongside the +2 Sword or the Sword of Paradise (Mystic Sword, only usable by the Avatar on NES).

If you look into the file named yew.tlk you will find the following text: "Mandrake root is found only in the Fens of the Dead and in the Bloody Plains where the ground is always damp."

So there is an NPC in Yew, that tells you about mandrake.

Is that line actually used in the game? Games have been known to contain unused content in their data files.

(By the way, in the NES version, there's a way to buy Mandrake Root (called Manroot in that version).)

There is a character who tells you this in the game, but no one tells you that it can only be gathered when both moons are new. That's what the OP is talking about.

I think you're supposed to figure that out on your own. Nightshade is a rare reagent and can only be found during new moons. Since mandrake is an even rarer reagent, it cannot be less elusive.

In all honesty, it feels like Mandrake Root is easier to get than Nightshade. In particular, Nightshade is on a tile that looks like every other tile around it (so you either need a sextant or to be good at counting), while the square with Mandrake Root sticks out from the surrounding terrain.

There's also the fact that, in the NES version, you can buy Manroot, but there's no way to buy Fungus (Nightshade).

Also, it might just be me, but it seems that none of the spells requiring Nightshade (in either version) are worth the effort of gathering it (except maybe Resurrection in the NES version).

I can remember playing Ultima 4 when I was 13 back in 1985. There were no clues online back then. I remember taking notes of everything said at every town. I remember finding both Mandrake and Nightshade. I know that I made the connections that what works for Nightshade will probably work for Mandrake. I also used the trick of the chest on the spot so I would not be poisoned. I do remember that there is a place that you could purchase both Mandrake and Nightshade so even if you could not find it you could still create and use spells that use it. I can even remember transferring characters from this game into Ultima 5.
Good times and good memories!

+1 There were very limited opportunities to collaborate before the interwebs.

All early gamers had was their time; making copious notes was mandatory, lest you encounter someone whom you discover has the second part of a clue when you have forgotten the first part … +1
It's a pretty natural leap of logic, either the same phase, or the opposite, or some other pattern. The moons are integral to the game.

(NES version spoiler here)

Speaking of mandrake root and cheating, I have, in a way, done this in the NES version.

In the NES version, the way you get the Sextant is by pressing Select in that one shop (note that this does not work in the pirate town's guild, unlike in other versions). A player, upon learning this, might think to try this in other shops, and it turns out that, if you do that in the reagent shop in the pirate town, you can buy Mandrake Root (called Manroot in the English translation) there. It's expensive, 20G each to be exact, but it is an option.

Now for the cheat: As you know, when you buy reagents, you are asked to count the money for the blind reagent seller; this means that I can buy 99 Mandrake Root, which would normally cost 1980G, for a measly 1G. Of course, this isn't virtuous (though the penalty isn't as severe as in other versions), but it can still be worth doing (in particular, I note that speedruns of the NES version do this); in this case, you can cheat the reagent seller out of nearly 2000G worth of reagents.

(By the way, this particular reagent shop lost its most notable trait from other versions: In other versions, Black Pearl is really cheap there (1G), but in the NES version, reagent prices are the same for every shop, and in particular, Black Pearl costs 9G everywhere.)

Like so many others here, I'm an old guy who played this in the 80's and into the 90's. Yes it took my buddy and me 2-3 years worth of playing and comparing notes and experiences to finally win. There was no internet, no walkthroughs, no forums, etc. Just me and my game manual. I think we may have found and bought a hint manual published by Origin, but that was mainly for mapping dungeons, as I recall.

There was one trick we learned from Compute! magazine (you old guys recall that one?) was the one where you could swap disks incorrectly when moving from Britannia to the castle (or vice versa?) and then gain a fortune in gold by raiding chests that now littered the landscape.

Otherwise, you just have to talk to EVERYONE, and search EVERY corner of every map to do so. Even an occasional non-hostile monster or two could talk give you a clue or two.

The NES version, which is the one I grew up on, came with a manual that had some hints for the game (and I believe maps of various areas), so that helped. (Note that not all the information in the NES version's manual is applicable to other versions, as there are major differences.)

It was not a cheat, it was in the game testing your honesty. It was a good way to get your reagents at a cheap price but your virtue was going down the drain. Then later, you would see him and pay the price, exit the place, reenter and buying again, and each time your virtue would increase. I recall when I was talking to the "virtue" guy, he was insulting me very badly. I also recall another one calling me a "coward", but I had figured out how it was working, and I took the proper measures to not lose my time getting the money. I recall having a pile of papers full of notes. Last month I installed Ultima 6 with DBGL. I am not sure I will have the patience to finish it. I only played a few hours and I dislike the perspective view. I solved Ultima 1 to 5, beginning with the 2 and the 1 being the last I had played. It was on an Apple 2E.

From WIKI;
Honesty: Truth
When purchasing goods from blind merchants, the player is required to enter the amount of gold they wish to pay. Although the player has the option of paying less than the merchant has asked for, this will mark the player as dishonest. Stealing gold from chests in towns, villages and castles will also penalize the player. This Virtue is embodied by Mariah the Mage.

The part that feels a bit like cheating is that it's too easy for you to get your virtues back up, so it makes sense to max out on expensive reagents early when money is tight, then later work on your virtues when money isn't as much of an issue.

It's also worth noting that money is significantly harder to come by in the NES version; the RNG is biased toward lower gold amounts from chests, and dungeons and (especially) dungeon rooms don't have as many chests to open. Also, the (possibly intended?) exploit of getting Mystic Weapons/Armor, selling them, and then getting more, doesn't work in the NES version (you can only get them once and can't sell them).

(By the way, in a speedrun it turns out that the most time-consuming virtue to raise is actually Valor, son one can't afford to run from random encounters (although, in the NES version, you can use Blink to bypass those that would take too long, or if you know you've won enough battles to reach Avatarhood).)

(Also, speaking of speedruns, Ultima 4's speedrun is actually rather long for an Ultima game, the longest out of at least the first 7 games.)

There is a single patch of swamp in the middle of the Bloody Plains. When the moons are in a certain configuration search and you'll find mandrake. You can use a trick to avoid getting poisoned constantly. Stand next to the patch and wait for a monster to show up and hopefully he'll stand on the patch of swamp. Once you kill him, they'll be a chest. DO NOT open it. Leave it there and you can stand on it without getting poisoned. Or if you have a lot of cure spells prepared, you can just move to the patch when the moons are aligned and get poisoned.

Nightshade is actually easier to find:
Here's a hint, If you wait on space outside of a certain shrine attached to the town of Minoc, at a certain time at night, you'll find Nightshade.