wheel - 4:54 pm on Sep 13, 2010 (gmt 0)
One data point. I registered a keyword rich domain in May 2010. Over July/August I got about 3-4 on topic relevant links, all with the exact anchor text of the domain name.
In the first couple of months or so it landed on about page 3 for the exact search. In the past week it has leaped to spot #2.
So, in this case, 1-2 months for a bit of effect, 3-4 months for full effect?