ActuaryTm, I might agree with you if this hadn't happened to me several times with OfficeMax rebates. They absolutely screw you by claiming you didn't submit in the appropriate time period, whether you did or not. These days, it's the weak link, because people keep copies of everything else, but it's hard to prove mailing date without having to make an unwarranted trip to the post office (often a 30 minute waste of time anyway).
In the past, I've called in and gotten things right every time, but it's never been for anything more than $20 or so. If this doesn't work, I would go to your local OfficeMax and talk with the manager. Be firm but friendly. They are trying to gip you out of your cash, and it's not right. It's one of the reasons I don't do rebate deals with OfficeMax any more. It's one thing when people send in "shady" rebate claims trying to get a rebate that's only for certain stores, etc., but these guys (the rebate company) are shady at best even when every condition of the rebate is followed faithfully.
[Edit]One more thing - ask them to fax you a copy of the envelope with the postmark date on it. There is some kind of law that states if a letter is mailed, it is legally assumed to have arrived at its destination. While that's not exactly in play here, this tactic has worked for me before.[/Edit]