I just went through that today. I got my SP3 replaced yesterday for a broken screen at the MS store. They transferred my complete to the new SP3, but the new one failed after using it for an hour. They did another exchange and didn't move my complete over. I spent an hour on the chat emailing them the receipts and documents proving I had it on there. Said will be done by next Monday.
I also had similar difficulties: I bought the Microsoft Complete plan from the online Microsoft Store, and it seems that the procedure never asks for the Surface serial number. At the end I found myself having bought some kind of "virtual token" with no apparent way of linking it to my Surface. What I did was calling the support, which was very kind and indeed fixed the issue, but took some days and requested me to upload the purchase receipt (despite the fact that I bought it from the Microsoft store, not somewhere else, but it seems that they don't have the best internal communication between departments).
Anyway they have always been very kind during the procedure and eventually fixed it. Also, both my standard and the Complete warranty are actually about three months longer than they should. The support guy said that they do this for organizational reasons and that he hopes I don't mind.