I've seen 6 months mentioned a lot, but in some of the information I've consumed I've heard that some people call their customer service as often as each month. I'm pretty sure they make notes on how often you call, and I'd hate for some stupid logging of my calls to lead to rejection.
I haven't started calling for rate reduction yet, but I'm planning on starting to call every 6 months on each card. If it's possible to get good results with more frequency I'd like to do that.
I've also heard of people calling when the "promotional rate" they get from their previous call expires. Is it possible to get a lower rate that close to ending a promotional rate? That seems unlikely to me.
Update 10/15/2010: Called Capital One today and got my rate reduced 7% for a 10 month period. At the end of the 10 month period, the rate will return to original rate. I plan to call again 8/15/2011 to try and get another rate reduction after the promo period has ended. Has anyone done such a thing successfully, or do they give you guff like, "Well...you know...you're just getting out of a promo rate so we can't do that at this time"?