Unable to delete Business Partners in CRM

I have used TCode BUPA_PRE_DA to mark a certain BP to status "to be deleted". The message said "Business Partner 123 has status 'Flagged for Delettion". When I went to delete the BP using BUPA_DEL, I couldn't do it. The message says, 'no business partners deleted'. I have SAP_ALL and SAP_NEW authorizations. Am I doing it the right way? What could be the issue? If there is an alternative, please suggest.

Vijay