@andyhull suggested interpreting the messages top-down reading from right-to-left instead of my left-to-right instinct. That would make the decoded messages:

Red Message:

A novice came to a master
A novice asked how to find
A solution to riddles hard
A reply from a master was
A novice should search through sand
A novice should so find a boulder
A novice should search through Air
A novice should find the sky
A novice should search through water
A novice should so find the river
A novice Was enlightened

Green Message:

Reading this text just right now

this is the wrong place

Blue Message:

(empty?)