I spent about 2 hours researching on how to do this but got no answer. People resorted to fancy stuff just to put links in their flash messages. I thought the answer was in the render method. I first tried to use it but it didn't work because you can't call render/redirect_to twice in the same action:
flash[:notice] = render :partial => "some/partial"
So I looked at the source and tried to figure out what it was in render that read the file and spat out the text. 10 minutes later, I got this to work:
flash[:notice] = @template.render(:partial => "some/partial")
So now I can use link_to and other nice view helpers in that partial and it will all render nicely in the flash message. :)