I bought my N810 from buy.com. No such problems and (at the time) 70USD under Nokia's quoted price (don't know about that rebate you had, though).

Asking for the number on the back of the card isn't uncommon. I've had it happen to me on a semi-regular basis if I am shipping to my office (which is NOT my billing address, hence the added scrutiny).

Martin