Some research, some facts, some speculation.
The "in memory" data structures used to hold the data displayed on the screen differ from the external data structures used to hold the data stored on disk.
The in memory data structures are highly intertwined making it difficult to change anything because seemingly trivial changes ripple throughout the in memory storage structure. (After all, there are more than a dozen views that have to be considered and I'm sure there are many references to offsets which consider a maximum field length of 255.)
So ... at some point in the past, the in memory data display structure probably mirrored very closely the external data storage structure including a notes field of 255 characters. But, for a variety of reasons, MS decided to implement a larger Notes field.
The implementation that had the least impact on existing in memory data structures and code was to set it up so that a larger piece of text could be stored externally and a small part of that data (up to 255 characters or a <cr/lf> -- whichever came first) was available for display on the screen.
(Remember, too, that there was a time when 640K was enough for everyone -- Gates didn't actually say anything like that but people believe it anyway.)
So, now there was the best of both worlds: an easily handled change to the in memory data structure (in other words: none); an easily implemented external data storage structure (in other words: the pop-up window with 6 tabs that you see when you double-click on a task) that let the user actually store significantly more information in the external data storage structure.
There was a drawback: the search function was designed to search the in memory data structure (which holds only the first 255 characters or until the first <cr/lf>).
MS had several choices: change the in memory data structure; change the search functionality; live with the constraint that search wouldn't find anything after the first 255 characters (or the first <cr/lf>.
They made the decision that I would have made: minimal impact and live with the constraint.
Only one question remains: when? I'd guess that it was very, very early on. Does anyone have Project 4.0 (or earlier) installed and running. The test is simple: which is the earliest release where double-clicking on the task opens a tabbed window that has a Notes field which holds more than 255 characters?