You'll have to forgive the multi-posting, there's simply no replies in-between..
I've made progress decoding the garbled data.
It was encoded in dYUV. This format also has an encoding size of 1 byte per pixel (actually 2 bytes per 2 pixels).
Long story short: this could not have been decoded without the Greenbook. The deltas were quantified using a custom function.
I've decoded many images (pieces of the map) using a working decoder (again home-brew in PHP).
Trouble is though, that I have yet to find the initial YUV values.
For some images they are assumed to be neutral grey (in this case YUV[128,128,128]).
But for images that are in a sequence (say two horizontally fitting pieces), the second piece has different initial values for Y, U and V.
Efforts so far have not yielded working results.
To show an example: the following two images are horizontally sequenced, but only the first image is properly decoded.
The left image, properly decoded
The right image, missing its initial YUV values, they are assumed [128,128,128]
One thing is noticeable though, and that is that the COLOR seems to be correct. This would make it seem like U and V values are always initialized at 128!
The search continues...
--Edit 13/12/'16--
Because this is going to be a small update, I've refrained from adding yet another post.
I've searched for the assumed initial YUV values that fitted the first image (the one I correctly decoded) and found them.
I searched for 0x808080 [128,128,128] repeated a few dozen times.
A datablob of exactly 720 bytes long is present twice closely following the map data itself (there's one blob in between them of unknown purpose, perhaps 'here you can walk'-data?).
Why 720 bytes? Each map is 240 lines by 384 columns. The linefeed (initial values) consists of Y, U, and V information. One byte each.
So that makes 3 bytes per line, for 240 lines -> 720 bytes.
Using this last piece of missing information, all map data was decoded. The overworld map file (over.rtf) contained 305 map pieces.
All but a dozen or so are part of the overworld. There's one additional map for each first area per shrine and one for each pre-boss area.
There's a few map pieces that are used to show the indoor areas (inside the houses of Skotness for example), but also the caves near the beach.
World map
Assembling the map was no easy task; many pieces were scattered in groups and some weren't as logical as they first seemed.
A tiny world map is stored in zelda.rtf in a CLUT like manner:
- Map - World Map.png (491 Bytes) Viewed 14966 times
Each pixel represents a map piece/area. And I suspect that the color differences are caused (not only by the CLUT I used) by the difference in background music.
I suspect that the underworld map file (under.rtf) contains the map data for all the shrines.
-- edit 30/08/'17 --
Reuploaded world map (moving forum removed attachments)