Long time lurker here ;-) If any movie deserves a special edition then I think Waterworld does. Theres two cuts of the movie and think of the "making of" documentary that could be created. There must be some stories about the production, I mean one of the sets sank!!
Anyway, I love your guys work on these edits and I know how you like to include as much as possible for bonus content. I'm surprised no one has mentioned the old Waterworld game by Interplay. I had to make sure I wasn't imagining it and found this page.
This is the part that I remember (although I only had a demo, never the full game):
• Experience never-before-seen footage from Waterworld the movie and interact with its character via original video scenes featuring the actual cast, costumes and set
Its just an idea.
PS I don't know if its any help but in the newsgroups is a HD 720p posting of Waterworld.