Interesting writeup on Wikipedia about the Philippines' claims over Sabah...what a legal minefield:
The Sultanate of Sulu was granted the territory as a prize for helping the Sultan of Brunei against his enemies and from then on that part of Borneo was recognized as part of the Sultan of Sulu's sovereignty. In 1878, Baron Von Overbeck, an Austrian partner representing The British North Borneo Company and his British partner Alfred Dent, leased the territory of Sabah. In return, the company was to provide arms to the Sultan to resist the Spaniards and 5,000 Malayan dollars annual rental based on the Mexican dollar's value at that time or its equivalent in gold. This lease was continued until the independence and formation of the Malaysian federation in 1963 together with Singapore, Sarawak and the states of Malaya. As of 2004, the Malaysian Embassy to the Philippines had been paying cession/rental money amounting to US$1,500 per year (about 6,300 Malaysian Ringgits) to the heirs of the Sultanate of Sulu.
The contract between Sri Paduka Maulana Al Sultan Mohammad Jamalul Alam, representing the sultanate as owner and sovereign of Sabah on one hand, and that of Gustavus Baron de Overbeck and Alfred Dent representing the North Borneo Company, on the other as lessees of Sabah, was executed on January 22, 1878. The Lease prohibits the transfer of Sabah to any nation, company or individual without the consent of His Majesty's Government ("Government of the Sultan of Sulu"). Although it is mentioned to be a permanent lease, it is contrary to international law, which states that the terms for a lease contract can only be for 99 years, as in the case of Hong Kong and Macau when these were leased to Great Britain and Portugal respectively, by China and subsequently returned after the expiration of the lease. This would make the lease on Sabah overdue by 130 years.
Less than a decade later, the Sultanate of Sulu came under the control of Spain and in 1885, Spain relinquished all of its claim to Borneo to the British in the Madrid Protocol of 1885. In spite of that, in 1906 and 1920 the United States formally reminded Great Britain that Sabah did not belong to them and was still part of the Sultanate of Sulu on the premise that Spain never acquired sovereignty over North Borneo to transfer all its claims of sovereignty over North Borneo to Great Britain on the Madrid Protocol of 1885. This is so because the Sultan of Sulu did not include his territory and dominion in North Borneo in signing the treaty of 1878 recognizing the Spanish sovereignty over "Jolo and its dependencies." North Borneo was never considered a dependency of Jolo. However, the British Government ignored the reminder and still annexed the territory of North Borneo as a Crown Colony on July 10, 1946. This was in spite of the fact that the British Government was aware of the decision made by the High Court of North Borneo on December 19, 1939, that the successor of the Sultan in the territory of Sabah was the Government of the Philippine Islands and not Great Britain.
On September 12, 1962, during President Diosdado Macapagal's administration (the father of the present Philippine president, Gloria Macapagal-Arroyo), the territory of North Borneo, and the full sovereignty, title and dominion over the territory were ceded by the then reigning Sultan of Sulu, HM Sultan Muhammad Esmail E. Kiram I, to the Republic of the Philippines. The cession effectively gave the Philippine government the full authority to pursue their claim in international courts. The Philippines broke diplomatic relations with Malaysia after the federation had included Sabah in 1963. It was revoked in 1989 because succeeding Philippine administrations have placed the claim in the back burner in the interest of pursuing cordial economic and security relations with Kuala Lumpur. To date, Malaysia continues to consistently reject Philippine calls to resolve the matter of Sabah's jurisdiction to the International Court of Justice.