So I've come up with an answer that I find sufficiently satisfying.
Institutional decay doesn't just happen
It's a common trope of fantasy that things 'just used to be better', which fits well with our intuition about real life. (An intuition, which as it happens, is often completely wrong). I think GRRM recognises and plays to this. The characters in the Age of Heroes (Bran the Builder, Symeon Star Eyes, Azor Ahai, etc.) are almost certainly nowhere near as epic as portrayed, if they ever existed at all.
In the absence of war and famine, societies typically flourish. If an institution is decaying, there has to be a reason for it. American manufacturing is in a decay because the Chinese can do the same for cheaper. Stamp collectors are a dying breed because no one uses the post for personal correspondence anymore, now that we have the internet.
So I reject the notion that the Night's watch are in a state of decay 'just because'.
To maintain the culture of an institution, a steady (and relatively small) stream of new members is necessary
New recruits to the night's watch do not initially share the values, nor understand the culture of the night's watch. By being in the minority, they can be forced to assimilate to the culture. Any new recruits who were previously members of a specific faction (they owe their allegiance to a specific lord or to the Seven) who might be inclined to bring their own value systems along can be quashed by the majority rest of the night's watch with little relative pushback.
However, when a cohort of new recruits becomes a significant minority or even a majority of members, that's when the institutional decay starts. The 'executive' of the night's watch - the commander, higher officers and all those responsible for management of the watch - no longer have the force of numbers to carry out arbitrary punishment. To punish a popular but harmful new recruit is to court violent reprisals.
There are many examples in the real world of close knit cultures being 'ruined' by too many new members. The first one that comes to mind is the september that never ended, referring to the state of the nascent internet in 1993. Before then, usenet users were primarily academics, and each year (starting in september) a new cohort of users would arrive, and would typically be disruptive for a while before learning the etiquette of usenet. In September 1993, the launch of AOL meant that the influx was much greater than before, and the 'old guard' was powerless to teach the new users the ways of internet etiquette.
A similar effect can be seen within broader culture when the Baby boomers came of age. A lot of the previous culture (both the good and the bad) of the people who lived through WW2 was rejected by the Baby Boomers, and because of their sheer force of numbers, that culture shift persisted.
So how did things change for the worse after the conquest?
To quote Maester Aemon in AGOT (his "Love is the death of Duty" speech):
In the days when the Seven Kingdoms were seven kingdoms, not a generation passed that three or four of them were not at war.
I think this is the key. With constant war comes a constant stream of defeated nobility heading towards the wall.
After Aegon's conquest, the dynamics change in two crucial ways:
- Wars are less frequent and much bigger
- Peace can last for longer than a generation
The end result of this is that the influx of quality recruits to the Night's Watch is very clumpy and unpredictable. Large numbers of new recruits will result in the decay of the culture and values in the ways that I explained above. When Maegor sent 2000 of the faith militant to the wall, that would have had a huge impact on the culture there, even though that 2000 would still have been in the minority at the time.
Turnover on the wall is high
The wall is not a good place for growing old.
There's not enough info in the books to make a reliable actuarial estimate on the mean lifetime of someone after taking the Black. It stands to reason though, that not many people would make it past 20 years of service.
During a time of long peace, the lack of quality recruits from defeated households could be disastrous. So the recruiters have to make up the shortfall with criminals, broken men and other such recruits who are unacquainted with discipline and following orders. I don't have any quotes with me to back this up, but I suspect the Night's Watch has always accepted and made use of criminals. However, these criminals can always be beaten into shape by the rest of the Night's watch.
The crucial change comes when the Night's Watch is forced, through a time of peace, to recruit primarily from criminals.
That changes the culture, and earns the Night's Watch an unsavoury reputation. As other have suggested, once the Night's watch is associated with criminals, this results in a positive feedback loop. Men of honour are less likely to see taking the Black as a noble pursuit, and Lords are more likely to see it as a fitting punishment for their criminals and prisoners. I think this goes a long way to answering why the Night's watch is depleted at the start of AGOT, but it doesn't completely answer it.
The Night's Watch is the only thing standing between the realm and what lies beyond, and it has become an army of undisciplined boys and tired old men
Because of the high turnover at the wall, you don't necessarily need to look for longterm declining trends to explain the low population. Recent events are sufficient.
As @Aegon mentioned in his answer:
You're incorrect in assuming that Robert's Rebellion should have provided fresh manpower to Night's Watch. Robert pardoned every Targaryen loyalist. People lost parts of their lands but none lost their heads or titles. The only Targaryen loyalists we see on the Wall were sent there by Tywin Lannister, presumably after the sack of King's Landing
I think that pardoning these Targaryen loyalists deprived the Wall of much needed recruits, and was likely one of the biggest contributors to the lack of men serving there. The preceeding loss of respect for the Black probably influenced Robert's decision, but an arbitrary decision it still was.
Which is why the Night's watch is described as such by Maester Aemon. It's missing the cohort of middle-aged men whose combination of experience and fitness the Wall needed most. The cohort that would have been filled 15 years ago had Robert made a different decision.