I checked in the source code of my posts and discovered that the plugin was adding nofollow only up to 4 links at each post. It should be adding it to all of them. But I think I know why.
The weird thing is that after I tested 6 "nofollow-like" plugins I saw the same weird behaviour: each time only 4 of all the links on the post had the nofollow parameter on its output (wp frontend of the post).
I think my link URls might be too long and wordpress is having some kind of issue processing them. Could you please check for me if there is a solution?
I pasted a slice of a typical post of mine that does that in here so you use as test content.