I recently came across a book entitled "The Collection of Historical Documents Related to Bilateral Relations Between China and Brunei Darussalam" printed by the World Affairs Press, Beijing, China. The publication of the book was to mark the 15th anniversary of the establishment of modern diplomatic relations between China and Brunei. The 15th anniversary is the modern times - because if you read through the book, you would realise that the first diplomatic relations between the two countries probably was at least 1,500 years ago when exchanges of envoys began with the Liang Dynasty. Between 502 - 519, Brunei had already been sending envoys to pay tribute to China.
The book's introductions were by both Foreign Ministers, HE Li Zhaoxing and HRH Prince Mohamed. The book is bilingual - both in Chinese and English. The Chinese version being the more authentic as the book is full of collection of historical documents and writings that have ever been published which has mentioned the country. The first document was written some 1,500 years back by a Yao Silian who was a writer and editor in the early Tang Dynasty (618 - 907) where he indicated that the then family of the King of Brunei can be traced back to an ancient Indian family name of the 1st Century.
Relationships between Brunei and China ebbed and webbed with the times and the different kings. Sometimes when Brunei was the vassal state of Majapahit, the envoys from China was treated with indifference. But when Brunei was on good terms with the Chinese Empire, Brunei was treated well. In 1369, Brunei was included on the list of countries exempted from China's Military Action.
The death of Sultan Abdul Majid described as Maharaja Karna in October 19th, 1408 was described. His tomb was only rediscovered in 1958 and there are photos in the book which showed the condition of the tomb when first discovered and the restorations which have taken place since. The Chinese have now built a proper park leading to the tomb. On the Brunei side, our historical authorities still have great difficulty in placing Sultan Abdul Majid as part of the Sultanate lineage - thus making His Majesty, 30th rather than 29th if you include Sultan Abdul Majid. But if the sultanate is traced itself back to the origin, then that would really make a very interesting history.
Based on the Chinese historical records, Champa (today's Cambodia - Champa was probably one of the biggest and most powerful empire in those days - Angkor Wat was the capital) probably had a hand in the country as most of the early records indicated that Brunei followed the Chenla's customs and traditions. Brunei was then a Buddhist or Hindu country and wasn't a Muslim country bearing in mind that Islam did not come to Southeast Asia until about the 14th or 15th century. Though a Muslim Chinese grave has been found in Brunei dating to about 900 - 1200 CE, where some historians have indicated that Islam could have come to Southeast Asia via China rather than via the maritime trade routes through Malacca much earlier.
The book is an interesting read and to read snippets about Brunei that go back some 1,500 years ago is really something. It tells you about where we come from and how we got here. Though unfortunately, I am not sure how to advise you how you can get hold of one. Mine came through the Ministry of Foreign Affairs and I would presume that you can get it through the PRC Embassy here in Brunei. But when you do get hold of one, read it through. If you can read Chinese, read the Chinese version. I have been told that that's more accurate rather than read the translation as names etc have to be transliterated and the effect is lost along the way.