This is my understanding of what happens.
Deleting a file removes its entry from the directory structure and frees up its storage segments so that other data can be written into it. That's all it does. If you don't put any other data on the card, the image is still there. You just can't reach it through the operating system. However, low level disk access routines can reach it. That's what recovery programs do.
Formatting wipes the entire directory structure and starts fresh. It does not delete the data associated with the files. I don't think either type of formatting actually wipes the memory. That's how the FBI sometimes can gather evidence on hackers. There are programs that will wipe memory. But you don't really need them if all you're using your cards for is photography.
When the operating system writes data to the card, it puts it in available segments. When you reformat, all the segments become available in sequence. If you delete one file, but don't delete all of them, you can get fragmented segments. So pieces of subsequent image files might be in several different places in memory. Theoretically this shouldn't matter, except that it might have an impact on read and write time. The idea of having fragmented files bothers me as I'm not convinced that the operating system is always perfect. So I reformat whenever I put a new card in the camera.
I have been asked to recover images from cards that have gotten corrupted when they were used in several different Canon camera models without reformatting. They were swapped repeatedly between xxD and xD models. Some people tell me that this is impossible, but I've had the cards in hand.