I've done NewEgg/Verbatim rebates once or twice before, and received the check(s) on time. I always carefully follow rebate instructions and make a photocopy.
After a product is shipped to you, you can go into your account online and select a printable view of your order. Yes, it has the price on it. Just print it out and include it with the rebate form with the bar code taped to it. Photocopy the latter as insurance.
I never had any trouble with NewEgg's service. Eric, you may have had a bad experience with NewEgg. I haven't though in 10-20 purchases. They usually aren't the lowest price, but they're not expensive, and fairly quick to ship.