With the two cards I have used for years now after confirming a sucessful download I have used the following methods approx 50/50 and have never had a problem;
a) Format the card in camera from the menu. b) With the card connected to a card reader simply delete the files and reuse the card without re-formatting in camera. I know some say this is wrong but never had a problem.
I have never tried and was never aware of the two button method you mention.
One thing that comes to mind is that are the files or perhaps just one in the batch 'protected' (locked). I was trying to delete a single file in camera the other day only to eventualy find I had somehow locked it accidentally, a feature I had never used before.