Personally, I've only never received one rebate, and that's because the fulfillment house the company used went out of business. I probably could have pursued it more, but it would have been too much trouble. Some rebates I've received have taken much longer than others. I know of one particular place where the "allow 10-12 weeks to receive your rebate" was completely accurate, as in the 11th hour on the 12th week. Others, though, have come back in as few as 2-3 weeks.
No matter what, though, always make copies of the documentation. For larger rebates ($100 or more), I would even consider spending the extra money to send them certified mail with a return receipt.