Well, here is the final answer. I have used great Jimmy idea (which unfortunately is not complete itself) and complete recursion function to work properly.

Based on interface:

string RemoveAllNamespaces(string xmlDocument);

I represent here final clean and universal C# solution for removing XML namespaces:

//Implemented based on interface, not part of algorithm
public static string RemoveAllNamespaces(string xmlDocument)
{
    XElement xmlDocumentWithoutNs = RemoveAllNamespaces(XElement.Parse(xmlDocument));

    return xmlDocumentWithoutNs.ToString();
}

//Core recursion function
 private static XElement RemoveAllNamespaces(XElement xmlDocument)
    {
        if (!xmlDocument.HasElements)
        {
            XElement xElement = new XElement(xmlDocument.Name.LocalName);
            xElement.Value = xmlDocument.Value;

            foreach (XAttribute attribute in xmlDocument.Attributes())
                xElement.Add(attribute);

            return xElement;
        }
        return new XElement(xmlDocument.Name.LocalName, xmlDocument.Elements().Select(el => RemoveAllNamespaces(el)));
    }

It's working 100%, but I have not tested it much so it may not cover some special cases... But it is good base to start.

I have found a couple of XSLT solutions to do this, both of which can conveniently be processed with xmlstarlet:

1. How to remove the namespace and its prefixes in an XML file using XSLT? - IBM
2. XSLT: Remove namespace prefix from elements - StackOverflow

In my worked example below, I've used the IBM code and saved it into the file xslt_ibm:

<?xml version="1.0"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
  <!-- https://www.ibm.com/support/pages/how-remove-namespace-and-its-prefixes-xml-file-using-xslt -->
  <xsl:output method="xml" indent="yes"/>
  <xsl:template match="/|comment()|processing-instruction()">
    <xsl:copy>
      <xsl:apply-templates/>
    </xsl:copy>
  </xsl:template>
  <xsl:template match="*">
    <xsl:element name="{local-name()}">
      <xsl:apply-templates select="@*|node()"/>
    </xsl:element>
  </xsl:template>
  <xsl:template match="@*">
    <xsl:attribute name="{local-name()}">
      <xsl:value-of select="."/>
    </xsl:attribute>
  </xsl:template>
</xsl:stylesheet>

If you consider your XML file to be saved in the file file.xml then this command will rename each element and attribute out of its namespace:

xmlstarlet transform xslt_ibm file.xml

Input (file.xml)

<md:EntityDescriptor xmlns="urn:_" xmlns:md="_"></md:EntityDescriptor>

Output

<?xml version="1.0"?>
<EntityDescriptor/>

Your XSLT removes attributes also, because you don't have a template that would copy them. <xsl:template match="*"> matches only elements, not attributes (or text, comments or processing instructions).

Below is a stylesheet that removes all namespace definitions from the processed document but copies all other nodes and values: elements, attributes, comments, text and processing instructions. Please pay attention to 2 things

1. Copying the attributes as such is not enough to remove all namespaces. Also an attribute can belong to a namespace, even when the containing element doesn't belong to a namespace. Therefore also attributes need to be created, like elements. Creating attributes is done with <xsl:attribute> element.
2. A valid XML document cannot contain an element that has two or more attributes with same expanded name but elements can contain multiple attributes with same local name if the attributes have different namespaces. This means that removing the namespace prefix from an attribute name will cause dataloss if there is an element that has at leas two attributes with same local name. Other one of these attributes will be removed (or overwritten).

...and the code:

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

    <xsl:output indent="yes" method="xml" encoding="utf-8" omit-xml-declaration="yes"/>

    <!-- Stylesheet to remove all namespaces from a document -->
    <!-- NOTE: this will lead to attribute name clash, if an element contains
        two attributes with same local name but different namespace prefix -->
    <!-- Nodes that cannot have a namespace are copied as such -->

    <!-- template to copy elements -->
    <xsl:template match="*">
        <xsl:element name="{local-name()}">
            <xsl:apply-templates select="@* | node()"/>
        </xsl:element>
    </xsl:template>

    <!-- template to copy attributes -->
    <xsl:template match="@*">
        <xsl:attribute name="{local-name()}">
            <xsl:value-of select="."/>
        </xsl:attribute>
    </xsl:template>

    <!-- template to copy the rest of the nodes -->
    <xsl:template match="comment() | text() | processing-instruction()">
        <xsl:copy/>
    </xsl:template>

</xsl:stylesheet>

You could also use <xsl:template match="node()"> instead of that last template but then you should use priority attribute to prevent elements matching to this template.

Try this

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;
using System.Xml.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string xml =
                "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?>" +
                "<mgns1:PlaceXmlMessage xmlns:mgns1=\"http://www.testing.com/\">" +
                    "<mgns1:xmlDocument>" +
                        "<HubChangeRequest version=\"1.0\">" +
                            "<TransactionReference>" +
                                "<AuthenticationID>TestSUPPLIERS</AuthenticationID>" +
                                "<AuthenticationKey>hidden</AuthenticationKey>" +
                                "<TransactionNumber>hidden</TransactionNumber>" +
                            "</TransactionReference>" +
                            "<MessageNumber>hidden</MessageNumber>" +
                            "<MessageCreatedDate>2016-03-01T12:31:31</MessageCreatedDate>" +
                            "<ReferenceNumber>ABC123456789</ReferenceNumber>" +
                            "<ProductDetails>" +
                                "<StockItem LineReference=\"123456/1\">" +
                                    "<NewStatus>Despatched</NewStatus>" +
                                    "<DespatchReference>3 PARCEL LINE</DespatchReference>" +
                                "</StockItem>" +
                                "<StockItem LineReference=\"123345/2\">" +
                                    "<NewStatus>Despatched</NewStatus>" +
                                    "<DespatchReference>3 PARCEL LINE</DespatchReference>" +
                                "</StockItem>" +
                            "</ProductDetails>" +
                        "</HubChangeRequest>" +
                    "</mgns1:xmlDocument>" +
                "</mgns1:PlaceXmlMessage>";

            XDocument doc = XDocument.Parse(xml);

            XElement placeXmlMessage = (XElement)doc.FirstNode;
            XElement secondNode = placeXmlMessage.Elements().FirstOrDefault();
            XElement hubChangeRequest = secondNode.Elements().FirstOrDefault();
            placeXmlMessage.ReplaceWith(hubChangeRequest);
        }
    }
}

I found the answer above to be helpful, but it didn't quite work for me. This ended up working better:

// Gets rid of all namespace definitions 
$xml_string = preg_replace('/xmlns[^=]*="[^"]*"/i', '', $xml_string);

// Gets rid of all namespace references
$xml_string = preg_replace('/[a-zA-Z]+:([a-zA-Z]+[=>])/', '$1', $xml_string);

This is a fairly common question, and a quick search turned up the following questions:

How do I remove namespaces from xml, using java dom?

Remove namespace from XML in Java

Perssonally, I think XSLT is the most obvious technique because this is exactly what XSLT was invented for ( XML-to-XML tranformations). I have successfully used this XSLT to strip namespaces (credit goes to https://stackoverflow.com/users/18771/tomalak):

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:template match="node()">
    <xsl:copy>
      <xsl:apply-templates select="node()|@*" />
    </xsl:copy>
  </xsl:template>

  <xsl:template match="*">
    <xsl:element name="{local-name()}">
      <xsl:apply-templates select="node()|@*" />
    </xsl:element>
  </xsl:template>

  <xsl:template match="@*">
    <xsl:attribute name="{local-name()}">
      <xsl:apply-templates select="node()|@*" />
    </xsl:attribute>
  </xsl:template>
</xsl:stylesheet>

You will find the Java code for executing that XSLT in both threads.

@Markus Freitag To override the behaviour of XmlSerializer you need XmlWriterSettings for override or remove XML declaration and XmlSerializerNamespaces for override namespace:

public static string ToXML(this T obj)  
{  
 // Remove Declaration  
 var settings = new XmlWriterSettings  
        {  
             Indent = true,  
             OmitXmlDeclaration = true  
        };  
  
 // Remove Namespace  
    var ns = new XmlSerializerNamespaces(new[] { XmlQualifiedName.Empty });  
  
    using (var stream = new StringWriter())  
    using (var writer = XmlWriter.Create(stream, settings))  
    {  
        var serializer = new XmlSerializer(typeof(T));  
        serializer.Serialize(writer, obj, ns);  
        return stream.ToString();  
    }  
}  

See full example here.