It's because you're not adding your namespace as you should. Rather than add it as an attribute after you create a node, add it as the namespace when you create the node:
Dim xdoc As New XmlDocument
Dim Root As XmlElement = Xdoc.DocumentElement
Dim xmldecl As XmlDeclaration
xmldecl = xdoc.CreateXmlDeclaration("1.0", "UTF-8", Nothing)
Xdoc.InsertBefore(xmldecl, Root)
Dim BooksNode As XmlNode
Dim ns As String = "http://www.Company.com.au/xml"
BooksNode = xdoc.CreateNode(XmlNodeType.Element, "Books", ns)
xdoc.AppendChild(BooksNode)
Dim BookNode As XmlNode
BookNode = xdoc.CreateNode(XmlNodeType.Element, "Book", ns)
BookNode.InnerText = ""
BooksNode.AppendChild(BookNode)
Dim BookNameNode As XmlNode
BookNameNode = xdoc.CreateNode(XmlNodeType.Element, "BookName", ns)
BookNameNode.InnerText = "Hitchhikers guide to the galaxy"
BookNode.AppendChild(BookNameNode)
Dim BookNode2 As XmlNode
BookNode2 = xdoc.CreateNode(XmlNodeType.Element, "Book", ns)
BookNode2.InnerText = ""
BooksNode.AppendChild(BookNode2)
Dim BookNameNode2 As XmlNode
BookNameNode2 = xdoc.CreateNode(XmlNodeType.Element, "BookName", ns)
BookNameNode2.InnerText = "The Power of one"
BookNode2.AppendChild(BookNameNode2)
Dim NsMgr As New XmlNamespaceManager(xdoc.NameTable)
NsMgr.AddNamespace("bk", "http://www.Company.com.au/xml")
NsMgr.PushScope()
Dim BooksNoNsPrefix = Xdoc.SelectNodes("/Books/Book", NsMgr)
Debug.Print("No Namespace prefix:" & BooksNoNsPrefix.Count.ToString)
Dim BooksNsPrefix = Xdoc.SelectNodes("/bk:Books/bk:Book", NsMgr)
Debug.Print("Using Namespace prefix:" & BooksNsPrefix.Count.ToString)
Xdoc.Save("C:\Temp\Test.xml")
Dim NewXdox As New XmlDocument
NewXdox.Load("C:\Temp\Test.xml")
Dim NsMgr2 As New XmlNamespaceManager(NewXdox.NameTable)
NsMgr2.AddNamespace("bk", "http://www.Company.com.au/xml")
Dim BooksNoNs2 = NewXdox.SelectNodes("/Books/Book", NsMgr2)
Debug.Print("No Namespace prefix:" & BooksNoNs2.Count.ToString)
Dim BooksNs2 = NewXdox.SelectNodes("/bk:Books/bk:Book", NsMgr2)
Debug.Print("Using Namespace prefix:" & BooksNs2.Count.ToString)