Thanks to Taylor Nelson for pointing out that Podocarpus macrophyllus, in the Conifer division, fixes nitrogen. In fact it has Rhizobium in the roots but does not have nodules and may not fix very much nitrogen. Edible fruit! Talyor also mentioned that some South American Proteaceae may fix nitrogen as well.
Perhaps my hypothesis still holds if we only count nodules, but this blows my theory out of the water a bit. Which is cool!