Agrabah: Somewhere in the "blue caves" in the Cave Of Wonders.
Monstro: Somewhere up top of one of the rooms.
Atlantica: Ariel's Grotto.
Traverse Town: Some number of puppies.
Halloween Town: Bookcase of Dr. Fink's.

I know some of them are vague, but that's the best I could do, sorry.