The biggest problem was that before the Targaryens, there was a constrant stream of wars between the sovereign kingdoms. It appears that 'taking the black' was indeed a viable alternative to being executed as a deserter, or for treason, or for being taken prisoner but with no-one to pay a ransom and so on. These conflicts generated a constant stream of fresh recruits for the Watch. However, after the Targaryens took power, these wars and conflicts tailed off and became very rare (the Faith Militant Uprising and the Blackfyre Rebellions aside), so the only recruits for the Watch were criminals and well-intending knights. The constant - or at least regular - stream of battle-hardened knights and soldiers basically dried up. So the Watch suffered numerically and qualitatively, leading to the situation in the books where the Watch has dropped to barely more than 1,000 men to hold 300 miles of Wall, and most of those are former criminals.
Robert didn't pay much attention to the Night's Watch, but I suspect that between him knowing Eddard and Benjen, he might have been talked into sending more support once the threat of Mance Rayder became clearer. Obviously events prevented that from happening.