I'm in _exactly_ the same situation. I'm going to try sending Amazon an e-mail about it, although the device was gifted to me from the US and I live in The Netherlands.
It really doesn't matter: get the call center on the phone, all they will ask for is the email address of your amazon account (the account which you registered the kindle on).
I suppose the registration contains the device ID, which gives them the possibility to recover the order number or something.