Are you sure those subs weren't coming from the kick? I've noticed in many of the tom fills on that album, there's a kick behind them giving them more punch.
Check out the toms during the whole intro section of "My Apocalypse" for example. Obviously not tons of sub lows, but those floor toms are quite beefy with low end (at least somewhat beneath 80Hz to my ears), and there are no kicks or bass guitar in there. I suppose it's not out of the question to think that Andy left some extra low end in the toms there just for effect, but I somehow doubt it...
It's a tricky one, because it most mixes there is no hole in the lows for the toms to take up. All we can do is either take those lows away or use the toms to duck the low-end of the rest of the mix.
I know what you're saying about the first thing, but I don't know if I totally agree about your second assertion. I think it comes down to relative levels. The bass can be sitting nice and full at a consistent dB level (while occupying a lot of low end space), but it's completely possible for a low tom to use some of that same low end space (probably a few decibels louder or at least compressed quite hard), so long as there is enough headroom to accommodate it. I know the mastering thing starts to come into play as well, but it's not like in mastering that the low end is brought up so high that there is absolutely no room for two things to share any low end space. I just notice a lot in my car, that on a lot of recordings I really dig, the kick and toms have a lot of low end energy that is definitely louder than the bass and stands out as necessary, and it is definitely in a shared frequency range...although the bass definitely does not lack sub lows. It's a tricky balancing act (or at least it seems so to a non-professional like me), but I don't think that low end is so cut and dry, so as to say that two things can't share low end space. Maybe that's not totally what you meant, so I don't mean to take your words out of context though...! Check out the mix on Daylight Dies' "Dismantling Devotion" as another good example. That bass sits really nice and full, definitely in that emotive sub-low range, but the toms and kick sound even bigger.
As for the debate about "kick below bass" or "bass below kick", to my ears it's pretty clear that the kick doesn't contain a lot of sub lows in metal. Those sound waves in that range are just too long to really work out very well when it comes to metal drum beats... It takes time and distance for those sound waves to complete a cycle (if that's the right way of putting it). I think the punch in a good metal kick is really coming from a shorter low end sound wavelength, while the bass benefits most from those longer sound wavelengths. I have to admit, I haven't mixed on a sub, but I have a feeling that if a "bass below kick" mix comes out sounding like too much of a constant "BOOOOOOOOOM", but the frequency balance of the bass guitar is good, then it may just be an issue of having the bass guitar too loud.
I would LOVE to hear Andy chime in on this, because I know he (and other modern metal mixers) have been accused of not having enough low end, and I'm wondering what his take on low end relationships between kick, bass, and toms is...