1. Get three chest (of course, no pole) in Remiem Temple Chocobo Race mini-games. (30 Wings to Discovery)
2. Bribe Malboro 540000 for 4-5 Wings to Discovery, Bribe Great Malboro 1200000 for 8-9 Wings to Discovery. (You cannot bribe Malboro Menace though)
3. Win against Shinryu (Overkill: 2 Wings to Discovery). Shinryu is an original creation and you need to catch aquatic fiends in Mt. Gagazet to unlock it.

EDIT: I'm not really sure about that bribe thing but I remember it to be like that.