I'm not sure whether the API provides access to any phone-specific unique IDs as I don't have API documentation in front of me. I imagine that an app could generate it's own UID and store it on the device at install time. As this value would be created by an application, it may be deleted when a device is factory reset or the app is removed.
Another avenue to investigate is whether you can get programmatic access to the IMEI (International Mobile Equipment Identifier) which should be unique per-device and non-changing. An IMEI is part of the GSM standard, it may also be supported by WCDMA but I can't confirm this.
Unfortunately I can't provide any code samples to help you as Windows Phone is not an API that I have specific knowlege of