They could have sprayed the parsley with BT which would kill the caterpillars. I have had good luck with buying organic parsley from Publix. It has never killed my cats. You do have to feed them a lot of it, though, since the nutrition factor goes down as soon as it's picked. I don't know if Publix would use the same distributor in Jacksonville, but it's worth a shot. Unfortunately, BT spray is considered organic since it is a naturally occurring bacteria, but so far I've had no problems with the stuff from Publix. I also used organic dill once from them because their parsley looked wilted.
Ken, do you not get Black Swallowtails in your area? Black ST cats are known as the "Parsley Worm" because it is one of their host plants. I'm surprised you've never seen one on yours.