As a starting place, you might look at the Legend Entertainment hybrid text adventures (like Gateway or Timequest), where they tried to update text adventures to the new GUI-and-mouse era.
Those long tall scrolling frames could be compressed into spinners (e.g.
http://i.stack.imgur.com/KYtFW.png or
http://i.stack.imgur.com/X1X9J.jpg) and placed at the bottom of the interface, each spinner coming into existence when the spinner to its left is finished.
So you could choose "open" in the first spinner, and the second will come into existence with the list of possible openable items, and when you choose "the box", the third comes into existence with the choices { ".", "and", "with" }. The command is executed when a period is chosen. (The spinners may need to start scrolling off the screen to the left to fit longer sentences, though.)
Note the dual sorting of the verbs in the Legend Entertainment interfaces, where the most common commands are sorted by frequency but the full range of commands is sorted alphabetically. That's a good compromise; you don't have to scroll much to find a common verb, but when you do have to scroll you find a verb more easily.
Thanks for the game examples! I do agree that the ever-expanding spinners is an idea worth of try. One thing that might be a good addition is a search field above the spinner so if you know it's rare verb starting with V, you can just jump directly to it instead of scrolling for ages. Also if I start structuring the sentence on the upper part of the screen, it doesn't matter if spinners go away as long as you can tap the part of the sentence you want to edit later on.
I actually was thinking about using spinners earlier but dismissed it partly because spinners are really boring visually
I honestly think your predictive text idea is the FIRST direction you should go in.
From a mobile point of view I can't think of anything that would be more convenient than that, and I also feel like it would guide the user to interesting gameplay - it's like when you go to google something and get distracted by an interesting choice in the suggested search drop down menu.
The player starts typing "I want to loot the body" but gets suggested "I want to lick the wall" and thinks "wait, I can do that!?"
I do agree. However the problem with predictive UIs is "muscle memory". Of course I'm not saying that this won't work, bit there's some research done about this, and the experiments that have been done with predictive OS GUIs and context menus have resulted in more frustration than productivity. I think this might be more of a communication/visual language issue combined with repetitive tasks. I'll need to experiment with this whether your brain can grasp it.