To which airspace does the border of two adjacent airspaces belong to? Consider two adjacent airspaces of different categories. For example, airspace G is up to 2500' and above this is an airspace D. The border is at 2500'. Which airspace are you in if flying at exactly 2500'?

I recall a definition by ICAO that said that the border between such airspaces belongs to the less restrictive one, but I can't find that document.
You recall correctly. That document is ICAO SARPs Annex 11 § 2.6:


  Where the ATS airspaces adjoin vertically, i.e. one above the other, flights at a common level would comply with requirements of, and be given services applicable to, the less restrictive class of airspace. In applying these criteria, Class B airspace is therefore considered less restrictive than Class A airspace; Class C airspace less restrictive than Class B airspace, etc.


(Emphasis mine.)