You're running into problems because you're trying to read elements in a namespace without specifying that namespace.
The last attribute of the XML, xmlns="http://www.dealerlink.us" defines the default namespace of the document as http://www.dealerlink.us.
You can fix that by prefixing your element names with the namespace like this:
string xmlstring = "<?xml version=\"1.0\" encoding=\"utf-8\" ?><ServiceResponse xmlns:xsd=\"http://www.w3.org/\" xmlns:xsi=\"http://www.w3.org/\" xmlns=\"http://www.dealerlink.us/\"><Response>REJECTED</Response><Message>ZIP OUT OF AREA</Message></ServiceResponse>";
XNamespace ns = "http://www.dealerlink.us/";
XDocument XDOC = XDocument.Parse(xmlstring);
string msg = XDOC.Element(ns + "ServiceResponse").Element(ns + "Message").Value;
Hope this helps,
Fredrik Bornander