We don't generally condone paid links here on SEOmoz, because we feel the risks often outweigh the rewards. However, Eppie fairly notes that they do (too often) work. The problem is that, even putting ethics aside, most people just don't do it very well.
I actually think Shane makes a good point - some of these links aren't really "everlasting" in the full sense of the word. Article marketing and paid blog posts often get archived quickly, and while the links continue to exist, they get rapidly devalued simply by moving in the internal structure. These paid networks have to continue to sell new links, and selling new links often means archiving old links and diluting existing content. So, if you pay once, expect your link to be treated like a 2nd-class citizen down the road. That's just the nature of that business, IMO. With a monthly fee, they can at least afford to keep your link active.
There are "paid" options that Google tends to not view as critically, such as:
(1) Editorially-reviewed directories
(2) Sponsorships and membership organizations
(3) Paid press-release services (although not really "everlasting")
People tend to only think of the big ones for (1) and (2) and often overlook niche directories, smaller organizations, local organizations, etc. The nice thing about the smaller sites is that you may be one of a half-dozen paid listings/sponsors, as opposed to one of 10,000 articles in an article-marketing network.
I'll leave this open as a discussion in case others have constructive suggestions.