I just arrived in the Calm lands, and did not go to train a Choco. Well I went directly to the Cavern, then came back. The Choco lady was in the Northeast corner, but I did NOT have to train one to ride.

Never happened to me before.