Let's go with the assumption you are using tokenization/encryption techniques sufficient to meet PCI DSS.
No we are looking at an abstract problem of can someone predict a value. The risk factor is that if the value can be guessed or follows a known pattern, one could then delete at will.
The issue of the GUID is irrelevant, because the attack vector is still a brute force attack. While knowing the pattern or algorithms used to create your unique id can certainly help reduce the possibilities to more of a dictionary-bounded attack, the knowledge of the ids ahead of time is not necessary to delete records indiscriminately.
You address the problem by implementing additional controls. First, if this is in a database, you have sufficient logging and transactions in place.
On the way to perform the deletion, there should be additional controls in place. Let's start for the user side: If the record is associated with the user, only the user should have the ability to delete his/her own records. If the user is not authenticated or does not own the records, do not allow the deletion procedure to continue forward. Does the user need to provide a special authorization? Is another variable set in the database or in a the session to allow the deletion (e.g., they need to authorize before the action goes throught?) If there is a sufficient risk, you can implement an out of band confirmation, such as sending a SMS message or maybe a confirmation via email is acceptable. In this scenario, its probably low risk if a user knowingly deletes their own credit card records because they can enter it in again later.
If you have strong authentication, authorization, and transaction controls it will limit the ability to indiscriminately delete values, even if they are known.
As an additional precaution, you may wish to implement heuristics and attack detection algorithms. For example, limit the number of deletions from the same IP address per day. Roll back transactions if there are too many deletions in a given day considering normal deletion patterns, etc.
It sounds from your description a simple POST command is being performed, I would ensure this only happens if there is TLS/SSL, the user is authenticated, there is a CSRF token in the request, etc. I would ensure that all deletes are logged and can be rolled back. Since the deletion would not result in exposure, you can also rely on a post-action notification to the users, "We Confirm you have deleted your credit card on file. If you did not do this, please contact us immediately" etc.