It is not a valid microformat, has never been proposed as a microformat and has absolutely no reason to ever be included within the markup of a page.

As far as I am concerned the origin of "Dofollow" is the name Denis gave his plugin to remove nofollow from WordPress comments back at the beginning of 2005.
No Nofollow has been around for just as long.

That means that dofollow is a product namethat has become synonymous with the movement against using nofollow links for all user generated content.

I really should update my list of dofollow and nofollow pluginsthough I am still using Lucia's Linky Love.

You should also be aware that using nofollow might not be a viable method of hoarding Google Juice / PageRank Sculpting.

The ultimate reason however for this not existing is it has no purpose - links by default are "dofollow"… Google and other search engines then decide whether they have value to their algorithms.

Not all links, even without a nofollow pass PageRank, or even help with indexing - one example of this is Google Buzz which I have had a test running on for months - as far as I am concerned links from Buzz do not pass PageRank, and can't help with indexing.

Noindex comes in various flavours.

Meta Noindex
X-Robots Noindex
Robots.txt Noindex

They don't all behave exactly the same, in fact I would generally ignore Robots.txt noindex as it seems to be the same as disallow which does not keep pages out of Google's index necessarily.

The origin of rel="noindex"? Probably people confusing the use of "noindex, nofollow" as a meta directive, and thinking you can do the same at hyperlink level.

You Can't

rel="noindex" does not exist, and it is logical that it doesn't exist.

If you have a document, there can be 100s of links to it. If one of those links has a link level directive on it, all the other 99 links would still count.
Nofollow makes sense at a link level - 99 votes instead of 100, but you can't have a document indexed only 99% of the time.

Thus if you see a plugin which includes rel="noindex" as one of it's features, stay well away.

If you run a website receiving 40M+ visitors a month and are using rel="noindex"… LOL

Seriously if you are using either/both of these, no harm done… Google/Yahoo/Bing ignore them, but it might be worth cleaning up your code.