I *have* tried this scenario and the result is exactly what I wrote - at least on my Vim and my Emacs 23.2.1.
I just tried it with "make emacs" and it worked as what you said, so obviously something is wrong with my configuration, I apologize for that.
Anyhow the behaviour you request is a non-trivial issue because it interferes with the fact that "r" expects a character and not a command. After pressing "r" and when waiting for that character evil is *not* in insert-state so *no* insert state binding is active. It is certainly possible to get the behavior you desire but it needs work. Furthermore the behavior in many situations has to be worked out:
What should happen if more than one column is selected? Replace each single character by the yanked text (i.e. multiple copies of the yanked text are inserted per line, one per character) or should the whole line be replaced?
What should happen if the yanked text is line-wise or even a block itself?
Yes, it's not trivial at all and may not be worth the effort, especially when there is workaround: select block -> "d" -> select block -> "I" -> "C-r "" to achieve what I wanted.
What you said is what is working in Vim, not what is working currently in Evil, however, I think what is working in Evil is even better and more useful. I hope you are not going to follow Vim this time, and I believe Evil has done better than Vim in this matter and I don't think we have to always blindly follow Vim even when we know it is not good in the specific situation.
If you guy's decide not to follow Vim here, than making "C-r" work in this situation will be even better.
I welcome any ideas to get evil better than vim, but I currently have no idea for a robust behavior of the feature you want. But feel free to provide one ...
Since what is working on my system is different from that in standard Evil of course you have no idea about what I was saying. Sorry about that. York