I suppose we can trace the East Asian system back to China. In the Chinese text Nine Chapters on the Mathematical Art 九章算術 (dating to 2nd C BCE at the latest if I understand correctly), we see this question and answer:
This looks like a likely precursor for the Japanese X分のY notation, with 之 simply translated の (which is of course extremely common). But I am not convinced that it actually says "twelve divided by eighteen" and "two divided by three". I would interpret it rather as "Twelve of eighteen parts" and "two of three parts" respectively.
In Christopher Cullen's translation of the Writings on Reckoning 筭數書, another Chinese text of similar vintage, his notes indicate that he agrees:
The topic of division naturally leads into that of fractions. When faced with the standard form of expression sān fēn zhī yī 三分之一, literally ‘one of three parts’ I have decided simply to write ⅓. It does seem reasonable to take the solidus line as relating 1 and 3 just as fēn zhī 分之 ‘of [ ] parts’ relates yī 一 and sān 三 in the reverse order. The term fēn 分 has been translated as ‘part’ rather than ‘fraction’; this seems closer to the usage of the text.
So I propose that your premise is incorrect: Egypt and China used essentially the same method to represent fractions. Your example is not "Five that was divided by three" but "five of three parts" -- which is obviously not an intuitive concept when you express it in terms of "parts" of an implicit (single) whole, since the result is more than one, but you can see how it could develop as an extension from terminology like "one of three parts".
One interesting way in which I could be incorrect is that all of the above is correct in terms of where the X分のY terminology came from, but most modern Japanese speakers (represented by you and Tsuyoshi) nevertheless do in fact interpret it as "Y divided by X" rather than "Y of X parts [of a whole]". In that case, the question would be, how did this reanalysis of the phrase arise in Japan? (And how about Korea and other nations in China's sphere of influence?) I bet the answer would be something to do with word order, in that case...