Just got off the phone with Nokia USA.

So apparently the rebate is based off of the Pre-Order date, and you ARE required to include a receipt with the rebate submission (even thought the rebate is not perfectly clear about this.)