The Red Key first appears in Paper Mario. It would be used to unlock the red door in the Crystal Palace. It would return in Paper Mario: The Thousand-Year Door to unlock the cage in the Great Tree to the Puni Elder's cage. It would be located in a storage room found to the west of the prison.
Related Threadshow do ya get the key on world 5-6 - last post @ Apr 13, 2008
Can't find key in 2-7! :( - last post @ Dec 29, 2006
how do u get the key in level 5-6 - last post by @ Jan 24, 2007
The Cat Costume Is Key To The Game - last post by @ Nov 8, 2013
2nd Floor Key? - last post by @ Jun 22, 2008