I think your guess is basically correct. Countercyclical effects appear to count for some of the negative relationship, but not a lot of it. I believe that they chose 1981 to 2000 in part because it covers full economic cycles (and, of course, allows for looking at whether decreases in tax revenues were associated with lower spending in future years, as the “starve the beast” hypothesis would predict).
Relatedly, here’s another puzzle from their paper: they also find that the level of federal spending and federal tax revenues was positive between 1949 and 1980. So why did the relationship between spending and revenue flip from being positive (i.e., consistent with the “starve the beast” hypothesis) to being negative (i.e, inconsistent with it)? Niskanen and Van Doren ask this question and propose the following tentative answer:
We do not know, but we suspect that the growing influence of the “supply siders,” who have a good case that high marginal tax rates substantially reduce economic growth, undermined the influence of the traditional fiscal conservatives’ commitment to a balanced budget. Suggestions are welcome.
I find this explanation less satisfying than their explanation for the negative relationship, but I must admit that I don’t have any better hypotheses. So let me repeat their plea for suggestions that could explain this.