Pink Puffs drop them. They are found in a certain room in the Lunar Subterrane. There is a 1/64 chance of encountering them in that room, they travel in groups of 5 and each has a 5/64 chance of dropping an item and a 1/64 chance of that item being a Pink Tail. In other words, it's real hard. Use Sirens to track them down easier.