When it comes to link exchanges and rel nofollow I can agree that it is a serious problem sometimes. I do a lot of exchanges and it's quite a big job keeping track of them all. But, it is a big job anyway, webmasters who wants to cheat can easily do it in a number of ways even if they don't use a nofollow tag. Unlinking the page after a while is something that has happened to me a few times. You have a link from a links page or a special page about your site and after a month or two it stops counting because it no longer has a link from the main site.
I agree that the problem with faulty links in blog comments and such should be solved with spamfilters or fast and hard moderation. Sometimes this works very well (Akismet is a favourite) but sometimes it doens't work at all, especially if it is orphan sites, sites that the owner left or forgot for some reason. This is of course a problem for the search engines, that you are posting in old forgotten blogs isn't a reason to show your site for the searcher, only the best content is a reason for that.
When it comes to SEO for new sites the only advice I can give is make serious link exchanges with serious link partners or build your own site network with related quality sites. The Digital points forum
is a great place to start if you look for exchanges.
Edit: I forgot to mention, I don't use nofollow attribute in most of my sites but it is quite demanding if you have a small forum and are the sole moderator to handle the sometimes huge amounts of fake members posting spam.