The IMEI thing is not a surprise, it has happened to me and everything was ok.
I would not count on getting the bootloader unlocked anytime soon.
If you have no documents Motorola will not fix it for free.
Are you sure you have a European Milestone and not an American version?
OT MaxDB, CD1, CD5, J5, GD96, ME45, T68i, X6, CX65, A925, E398, MPx200, X6-2, OT715, D600E, W810, M600i, BB8100, W880, N95-2, P1i, Ignito, W880, X1, MS1, MS2, TP851, XT910, GTab 10.1, SGS3, Galaxy S4, Galaxy Note 10.1