There is almost always a red mandrake growing behind the rightmost tombstone in Nightside.
If you don't have access to Nightside, go to Haunted Cave and lurk around either the Nightshade's Tower end or the triton ave tunnel end. I've seen mandrake in both locations although it's not as "guaranteed" as the Nightside ones. Sometimes you get an ore or a chest instead.
If you have gotten access to nightside already, you have the perfect place to farm reagents. There is usually a mandrake on either side of the Death School house. One next to the tree, and one on the backside of the school. If you have a level 30 or so wizard, you can go inside sunken city and farm the different areas there. I went into sunken city once, soloed it, and got 10+ mandrakes in less than 45 minutes.
Another good place to look is Cyclops Lane, in Festival Park, right behind where Rand Taymore is standing. About half the times I go through there, red mandrake.
If you don't see it there, try this: go to Firecat Alley through the Dark Cave. As soon as you enter Firecat Alley, look on the lawns on either side of the cave entrance. There's almost always either an ore, or red mandrake.
The third place I always look is in front of Forlorn Tower (Melweena Smite's dungeon) on Firecat Alley's U-curve that overlooks the edge of the world. As you approach the tower, look on the right front lawn for red mandrake and the left front lawn for mist wood.
You could also try hunting around Colossus Blvd's various towers and castles for lawn mandrake.
In Azteca, the Zocalo has two places that regularly have either mandrake or black lotus. Around the fountain in Three Points, or next to the canal leading to Saltmeadow gate (cross the bridge and make a hairpin turn to the left to find the reagent).