Are you playing the North American or PAL version? You can only fight them in the PAL version.

Nope, the chocobo race'll only give you one load of Wings to Discovery. Any monster in the monster arena might give you a couple of Dark Matters if you Overkill them, so you just gotta keep fighting and hope. To get Wings to Discovery you have to get powerful enough (and rich enough) to keep fighting Shinryu over and over; he will usualy give you W.T.D's.

If you start at the Mushroom rock entrance, just go right down to the end of the Old road at the Mi'ihen Highroad, and there's a box. It's pretty hard to miss.