I decided to start a new survival map and try to play through to The End and defeat the End Dragon. I built a fortress with crops on top and animal pens outside. I dug mine shafts for construction materials. I built a nether portal, found a Nether Fortress with netherwart and blazes with blaze rods. I even beat carrots and potatos out of zombies and put them on the farm.
At that point I decided I needed melons (for potions). I explored a series of abandoned mineshafts I noticed intersecting a chasm I'd discovered during my mining operations.
i explored it for a week.
I got no melon seeds.
I wrote a program which scans the world files for chests and totals up their contents. There were no melon seeds.
I created a FRESH WORLD and ran in the four cardinal directions out to x|z = ±5000. I ran the chest scan and here are the results:
I have a 1.6.2 single player world going and I found melon seeds in a mineshaft, and I recently found some in a dungeon. I find them a lot, actually, now that I don't need them any longer. It took me a few chests before I found them initially, though.
I have a 1.6.2 single player world going and I found melon seeds in a mineshaft, and I recently found some in a dungeon.
Then something odd is going on. I did some more tests creating worlds using version 1.5.2, 1.5.1, and 1.4.7.
Out of over 200 chests in each world, only chests generated by 1.4.7 had any melon seeds inside.
Hypotheses that could explain the difference between my results and your results:
1) defect in my scanning program. (less likely now that I've actually demonstrated finding seeds in a chest)
2) something bad about my chunk generation method (I switch to creative mode and fly over the terrain for long distances)
3) your chests were generated by a different terrain generator than 1.6.2 (maybe you started the world using a 1.4.7 version and are still playing it in 1.6.2, but it seems unlikely that you would overlook that when presenting your counterexample).
4) melon seeds don't spawn in chests near the X and Z axes.
5) only those 20 objects in my results are placed in the chests when the chests are generated and melon seeds don't appear till a player first opens the chest.
6) melon seeds are generated in chests in 1.6.2 and the RNG prevented any from appearing in the 888 chests I surveyed in my second experiment.
7) the world seed influences what spawns in a chest and I had a string of really unlucky random seeds (which means some single-player worlds are quite doomed).
If you're going to provide counterexamples, please ensure that #3 is not in effect (that your world is fresh and has no chunks from older terrain generators).
No, fresh world started in 1.6.2 for the horses. I picked a seed from the seed area of this site that had horses at spawn.
I don't know about everything else, and I'm not trying to say your program is faulty or anything like that. I'm just telling you what I found in my world, that's all. Maybe they're much more rare or something and I just got lucky.
ETA: I think you got your answer from Mojang on your bug report page. Melon seeds now spawn in minecart chests since 1.5, not regular chests.