Maps in vanilla/Boom format have very strict limits on their complexity. From the symptoms you describe, it sound like you have too many segs (more than 32768). Note that this limit is not related to the drawsegs limit displayed by Visplane Explorer, so it wouldn't have helped you in any case.
Nodes are probably the most difficult thing to understand in Doom editing, which is good because you don't need to understand them. They store your map's binary space partition tree, which is used to speed up rendering by providing a way to quickly determine which walls are in front of which other walls, without having to calculate the distance to each wall (I can explain how, but it's not really relevant to this problem). It requires that all sectors be broken up into convex pieces, called subsectors, which are composed of line segments (segs). It is these line segments which you cannot have too many of. Your map will have at least one seg for each one-sided linedef, and at least two for each two-sided linedef, and will have more if your sectors need to split up into multiple subsectors (which requires that these sectors' linedefs be split into multiple segs). If you have more than around 10,000 linedefs or so, you are very likely to hit the 32,768 seg limit, and your nodes cannot be built.
Vanilla Doom and Boom will behave extremely strangely on a map with invalid nodes, and it is absolutely required that valid nodes be produced if you want to claim vanilla/Boom compatibility. There is no solution other than to greatly reduce the complexity of your map.
EDIT: Hmm, I may be wasting everyone's time here. The map I'm talking about is for the Panophobia megawad which is supposed to be vanilla-only. However everyone else is making maps in Boom format, I am the only one making them for Doom 2. When I save the map in Boom format it sometimes doesn't give the node builder error.
This has nothing to do with the problem. Boom actually uses the same map format as Doom, just with some extra linedef types and such (Doom's map format supports linedef types in the range 0-65536, even though vanilla Doom only uses values in the range 0-140, so there's plenty of room for expansion without changing the map format). Boom increases the drawsegs limit (the number of segs that are visible at once), however the total number of segs that can be stored in the map is unchanged. What's probably happening is, your map is only just on the limit, and extremely minor changes are enough to (sometimes) bring it under the limit. It is not related to whether you're saving your map in Doom or Boom format.