← Blog/Guide

GDPR Deletion of Personal Data: Steps, Rules and AI Calls

Semir JahicSemir Jahic··19 min read
GDPR Deletion of Personal Data: Steps, Rules and AI Calls

An email arrives on a Tuesday morning while you're on a job or between patients: please delete everything you hold about me. You recognise the name. There's an appointment in the calendar, a call recording from three weeks ago, a transcript, an AI-written summary sitting in your inbox, an SMS reminder that went out, a row in the CRM, and somewhere a backup nobody has opened in a year.

Two instincts fight each other. One says delete the calendar entry, reply "done" and get back to work. The other says touch nothing until a lawyer answers. Both are wrong, and both cost money. Erasure requests are routine for any business running a phone line in Europe: in the European Data Protection Board's 2025 coordinated enforcement work, erasure requests represented approximately 19% of all complaints received in both the Netherlands and Luxembourg, and a Dutch corrective action imposed a €6,000 fine on a controller that ignored removal requests and lacked an effective method for handling them, according to the EDPB's 2025 report on the right to erasure.

Handling this well isn't about memorising a regulation. It's a repeatable routine: decide whether a ground applies, work out what you may lawfully keep, trace every copy, and write back inside the deadline. A small firm can run that routine with an AI phone assistant doing most of the tracing, as long as a person builds the workflow before the first request lands.

When GDPR Requires Deletion of Personal Data

Every request you receive is a decision about one of five grounds. Article 17 of Regulation (EU) 2016/679 has applied since 25 May 2018, and it gives people the right to have their personal data erased "without undue delay" when one of those grounds is met. The adopted text of Article 17 sets them out, and they cover almost everything a plumber, clinic or agency will ever receive in writing.

Read the request against the table below before you touch a record. Each row is a legal ground, a typical small-business example, and the action it forces.

Erasure grounds under Article 17
GroundTypical exampleWhat you must do
Data no longer needed for its original purposeOld job enquiry kept after the job closedErase or restrict once the purpose ends
Consent withdrawn and no other legal basisMarketing list signup withdrawnStop use and erase unless another basis exists
Successful objection to processingCustomer objects to profiling of their callsErase unless you have overriding legitimate grounds
Unlawful processingRecording made without a lawful basisErase and document the unlawful processing
Deletion required by EU or member-state lawCourt or regulator order to remove recordsErase as the law requires and record the order

The three questions that decide any request

  1. Does a ground apply? A person saying "delete it" isn't the same as a ground existing. Read the request, then match it to a row. If none fits, you still owe a clear answer explaining why, not silence.
  2. Is there a basis that lets you keep part of it? Very often yes, for a narrow slice such as an invoice or a complaint file. That slice gets separated, restricted and named in your reply.
  3. When does the clock stop? The decision and the reply both fall inside a statutory window, and the date you received the request is the anchor. Confirm the person's identity first, because verification time counts.

A deletion request is not a command to erase every trace of a person from your systems. Article 17(3) preserves processing that's necessary to comply with a legal obligation, protect public health, perform official tasks, or support public-interest archiving, scientific or historical research and statistical purposes. The table tells you whether you owe a decision. It doesn't tell you what you may keep, or how fast you must answer.

Deadlines and Exemptions That Let You Delay or Refuse

The date stamp decides more than the wording. Under the ICO's guidance on the right to erasure, you must respond without undue delay and normally within one month, and that period can be extended by up to two additional months for complex or numerous requests, provided you inform the person inside the first month and explain why.

Use the extension when scope is hard: several people named in one request, a call archive nobody has mapped, recordings and transcripts still being separated from invoices, or a live dispute that needs legal review. In the boiler-repair case below, more time is defensible while the firm separates conversational data from the complaint file. It is much weaker if the only complexity is that nobody checked the inbox.

A valid ground also does not turn the whole file into debris. The EDPB's practical guidance for SMEs keeps the kept slice narrow: hold only what a specific legal duty requires, restrict evidence kept for a live claim to that claim, document any public-interest or public-health basis by scope, and assess journalistic, academic or artistic material case by case. The mistake enforcement work keeps finding is treating "legal obligation" as automatic instead of testing the record, the purpose and the retention period.

What partial deletion looks like in practice

Say a two-van plumbing firm gets a deletion request from a customer whose boiler repair ended in a complaint. Trace one caller through the stack: telephony log and caller number, AI assistant transcript, call recording, call summary, CRM or job-card entry, email summary, SMS summary, invoice, complaint correspondence, and the next backup cycle.

The recording and transcript go once the job and internal review are closed. The email and SMS summaries go with them if they only repeat the conversation. The invoice stays because tax rules require it. The complaint correspondence stays because it may be needed to defend a legal claim, with access limited to the person handling that complaint. The CRM entry is reduced to the kept slice rather than left as a full customer profile. Backups are handled by suppression: the record is deleted from live systems, marked so it is not restored into use, and cleared when the backup rotates.

That is a defensible outcome. Two shortcuts destroy it.

  • Treating "legal obligation" as a blanket override. It covers only the records a specific duty requires you to hold, for the period that duty sets.
  • Promising real-time unconditional deletion. If the assistant, gateway, CRM or archive cannot purge on request, the promise becomes the complaint.

A clean decision names each kept slice, the exemption behind it and the review date before the outcome letter is drafted.

How to Trace and Erase a Request Step by Step

Run these steps in order on the next request. Each one carries the reason it exists and the mistake that usually happens at that point.

  1. Verify the requester. Match the person to the record through the phone number or email already on file, and never read personal details back to an unverified caller. Erasure is destructive, and a wrong match destroys someone else's data. The common slip is accepting a request from a spouse, colleague or assistant without checking authority.
  2. Log the date received. Open a dated entry the moment the request lands, including the channel it came through. The statutory clock runs from receipt. The slip is treating a Friday voicemail as received on Monday, when the inbox was first checked.
  3. Build the request ledger. List every place the person's data appears: caller number, name, appointment details, transcript, recording, CRM entry, email summary, SMS summary, each with a purpose and retention rule. The slip that sinks most first attempts is deleting only the assistant's own record.
  4. Decide per data store. Erase, restrict, or keep with a named exemption, and write the reason next to the decision instead of holding it in your head.
  5. Execute and notify processors. Delete in the primary systems, then instruct each provider in writing and ask for dated confirmation. Never assume a dashboard deletion reached the telephony provider, the email archive or the analytics export.
  6. Write the outcome to the requester. Send the short letter within the month, covering what was erased, what was kept and why, the date, and the right to complain. A one-line "done" gives the person nothing to check and gives you nothing to show a regulator.
  7. Store a minimal record. Keep the decision, the date and the confirmations, not the deleted content. Keeping the original request email with all its detail inside the audit folder recreates the profile you just erased.

Most of this is automatable, and GDPR compliance automation covers how intake, logging and processor notification fit into one workflow. If the phone system is rednea, call data is processed on your instructions and retention is configurable, so the deletion step runs on your timetable rather than the vendor's.

A step-by-step instructional infographic showing how to trace and erase a user request from logs.
A step-by-step instructional infographic showing how to trace and erase a user request from logs.

Fill the ledger in before you write either letter, so the reply describes reality rather than intention.

Request ledger by data store
Data storeAction on request
Caller numberErase or restrict
NameErase or restrict
Appointment detailsErase unless a legal duty applies
TranscriptErase
RecordingErase and delete every stored version
CRM entryErase or keep only required invoice fields
Email summaryErase from the business copy and request provider deletion
SMS summaryErase and request gateway deletion
Outcome letter: Dear [name], we have completed your request to delete personal data received on [date]. We erased [categories erased]. We kept [category] because [legal reason], and access is restricted to [role] until [date]. You may complain to your national supervisory authority if you disagree with this decision.
Refusal or partial response: We cannot erase [category] because [specific Article 17(3) exemption]. We will delete it when [condition ends].

A complete file at the end holds three things: a dated log showing when the request arrived and what was decided, written confirmations from every processor that touched the data, and the outcome letter with its date. Nothing else needs to survive, and the less personal detail the file holds, the better it survives a review.

Storage Layers Where Erasure Usually Fails

Deleting the row is the easy part. The hard part is everything the row left behind. The US National Institute of Standards and Technology defines media sanitization as rendering target data infeasible to access or reconstruct for a given level of effort, and separates logical clearing, purging and physical destruction in its guidelines for media sanitization.

Encryption changes the economics of this. Where storage is properly encrypted, cryptographic erase purges data by destroying or blocking access to the encryption keys, leaving ciphertext nobody can read. NIST notes that this can give high assurance much faster than overwriting or physically destroying media, which matters when the media in question is a replicated cloud bucket.

Storage layers and how to erase each
Storage layerTypical data heldErasure method
Primary databaseCaller record, appointment, CRM fieldsDelete or overwrite the record, then verify the row is gone
Object storageCall recordings and voicemail filesDelete the objects and every stored version
Search indexTranscript text and keyword entriesRemove the documents and purge or rebuild the index
Caches and queuesSession data and pending messagesExpire or flush entries tied to the person
Logs and analyticsEvent records, dimensions and error tracesPurge events or pseudonymise them where feasible
Email and SMS summariesForwarded summaries in inboxes and gatewaysRequest deletion from providers and record any copy you cannot reach
Backups and disaster-recovery replicasSnapshots of all the aboveSelective erasure, key destruction or controlled expiry

Keys, tombstones and the re-import problem

Per-record or per-tenant encryption keys are the single most useful design decision here, because destroying one key erases one person's data across every copy that used it. End-to-end encryption is the precondition: if the data is encrypted end to end, key destruction is a genuine erasure method, and if it isn't, you're back to overwriting files one by one.

Tombstones solve the second problem. A stale integration, a nightly sync or a disconnected calendar feed can re-import a record you deleted last month. A tombstone marks the identifier as erased so the sync refuses to recreate it. Immutable deletion events log the action so nobody can rewrite history later.

Where each layer physically sits matters as much as how it's deleted, and where your AI receptionist's data is stored covers the hosting questions worth putting to a vendor.

Backups need a documented strategy, not a shrug. You have three workable options: selective erasure inside the backup catalogue, key destruction with assured key isolation so the backup ciphertext is unreadable, or controlled expiry with a restore procedure that cannot reintroduce the subject's data. Pick one per system, write it down, and test a restore before a regulator asks.

For each deletion, record the scope, the timestamp, the result in each system, the processor acknowledgement and the backup expiry policy. Keep the audit record itself thin, because an audit log stuffed with names and numbers becomes a second copy of the data you were asked to remove.

Why Pseudonymised Records Still Count as Personal Data

Replace "Jane Smith" with "Customer 104" and the file looks clean. It usually isn't. The shortcut only works if the business cannot reconnect the code to the person, and in most small firms the lookup key sits in the same CRM, one column to the right.

The regulators are watching this specific move. In the EDPB's 2025 coordinated action, 32 European data-protection authorities examined how 764 controllers handled Article 17 requests, and inefficient anonymisation was identified as a recurring problem when organisations used it instead of deletion, as the EDPB's announcement on the right to erasure records. Pseudonymisation, swapping a name for an internal code, does not normally end GDPR obligations while you keep the key.

The reidentification test for a call record

Ask whether the person could still be identified from what remains, using means reasonably likely to be used. For a phone call, run through the obvious routes:

  • The conversation itself. A caller who says "it's the flat above the chippy on Mill Street" has identified themselves without a name field.
  • The phone number. A mobile number is an identifier on its own, and it's attached to the recording metadata.
  • Appointment details and location. A time, a service and a postcode narrow a population to a handful of people.
  • Voice. A recording that captures a voice is not anonymous, which is why any biometric profile built from it raises the stakes considerably.
  • The linked customer record. If the appointment ID joins back to a named CRM entry, nothing about the record is anonymous.
If the record fails the test, handle it as personal data and delete it. Aggregates are the only thing worth keeping.

The boundary isn't fully settled either. The EDPB is developing anonymisation guidance in light of recent Court of Justice clarification, so treat generous claims about "anonymised call data" with suspicion, including your own. Keep aggregated statistics, such as monthly call volumes by service type, and document them separately from the individual file so nobody confuses the two.

Controller and Processor Duties for Deletion

Your business is the controller. You decide whether the ground applies, what gets erased, what stays under an exemption and what the person is told. Each provider that stores or handles the data on your behalf is a processor and must act on your documented instructions, which means an instruction you never send is a deletion that never happens.

Keep evidence at both levels. On your side, the request log with the decision and the reasoning behind any retention. On the processor side, a dated written confirmation of what was deleted and when. A vendor's support ticket saying "removed" is weaker evidence than a confirmation naming the data categories and the systems.

What the contract must say about sub-processors

Sub-processors are the providers your providers use, and they're where deletion promises can break. The Data Processing Agreement should require each one to erase data when instructed and to confirm in writing, with that acknowledgement passed back up the chain to you.

A workable model looks like this. The provider publishes a sub-processor list, gives at least 30 days' notice before adding one, and lets you object under the DPA. Where a recipient isn't certified under the EU-U.S. Data Privacy Framework, the contract relies on EU or UK Standard Contractual Clauses instead. Rednea works to that pattern: Google LLC, Vercel Inc. and Telnyx are certified under the EU-U.S. Data Privacy Framework, and Standard Contractual Clauses are in place for sub-processors that aren't.

Keep the sub-processor list and its notice dates with your records. When the list changes, your deletion map changes with it, because a new provider means a new place a transcript might sit. Customer data protection covers the wider set of controls that sit around this.

Before you sign with any vendor, get three answers in writing:

  1. Where is the data stored, including replicas, backups and any regional failover?
  2. Which sub-processors touch it, and how much notice do you get before that list changes?
  3. How is deletion confirmed to you, in what format, and within what timeframe?

Treat each answer as something to verify in the contract rather than an assumption to carry into an audit.

Handling Deletion Requests on an AI Phone Assistant

A caller dials, gets a natural greeting instead of hold music, and says: "Delete everything you have on me." That sentence can arrive at 9pm on a Sunday, and the assistant is often the only thing answering.

Its job splits into three parts. A deletion request can arise from several situations at once, including data that's no longer necessary, processing that was unlawful, withdrawn consent, or a successful objection, as the EDPB sets out in its guidance on respecting individuals' rights.

A person using a smartphone to request permanent deletion of their personal data through an AI assistant app.
A person using a smartphone to request permanent deletion of their personal data through an AI assistant app.
  1. Verify. Call back the number on file or ask for a booking reference. The assistant must never read records aloud to an unverified caller, and must never confirm whether a name exists in the system.
  2. Log and route. Create the request, stamp it with the date received so the month starts running, and push it into the deletion workflow. Flag anything unclear to a person: disputes, requests from third parties, and any question touching a legal hold.
  3. Confirm. Send the outcome in writing through the email or SMS summary channel the business already uses, using the letter template from the earlier walkthrough.

Where the assistant stops and a person starts

Routine deletions of one caller's data can run without staff involvement: the ledger is fixed, the stores are known, and the decision is mechanical. Anything requiring judgement goes to a named human, which is the point of pairing automation with people rather than replacing them. The assistant absorbs the volume and the odd hours; a person owns the edge cases and signs off the letter.

That matters more as businesses serve customers in several languages. An assistant that handles the request in the caller's own language, then hands a structured summary to staff, removes the awkward step where a caller gives up because nobody at the firm speaks their language well enough to take a deletion request accurately.

Before you rely on any vendor here, confirm four things in writing: which data the assistant stores, whether it creates voiceprints or biometric profiles, whether call data can be deleted on request, and how that deletion reaches the telephony provider. Rednea creates no voiceprints and no biometric profiles, stores only what's necessary, and can delete all of a customer's data in real time on request, including call data, transcripts and recordings. For the UK angle, including recording consent and ICO expectations, see AI receptionist UK GDPR and ICO PECR rules.

Test Your Deletion Process Before the Next Request

Complaints become cases at volume. Ireland's Data Protection Commission processed 11,091 new cases in 2024 and resolved 10,510 of them, according to McCann FitzGerald's summary of the DPC's 2024 annual report. A process that only works in theory is a case waiting for a date.

So run one mock deletion this week, on a live test line rather than on paper. Create a test caller with a booking, a recording, a transcript, a CRM entry and an email summary. Send the request through the actual channel, then execute the workflow and check every store in the ledger plus the processor confirmations and the outcome letter.

The pass or fail checklist

  • Every storage layer cleared, including the caches and the exported summaries, not just the database row.
  • The search index purged, so a query on the caller's name or number returns nothing even after the underlying record is gone.
  • Every processor confirmed in writing, with a date and the categories deleted.
  • Backups covered by a documented erasure or expiry policy that survives a test restore.
  • The whole run timed end to end, from the request landing to the last processor confirmation, so the one-month deadline holds even when a real request arrives in a busy week.

Record the result and the date. When a test fails on the assistant or telephony side, the gap usually sits in the chain rather than the intent: the assistant deletes its own records while the telephony provider keeps its copy, or an exported summary falls outside the retention setting. Correct that step in the workflow and run the test again.

Repeat the test whenever the sub-processor list changes, because a new provider is a new place data can hide. The first real request should not be the moment you discover the gap.

---

When a customer asks you to erase their data, the difference between a routine afternoon and a regulatory complaint is whether your phone system can find and delete what it holds. Rednea answers calls around the clock in English, Spanish, French, German and Italian, books appointments, and sends the summary your team needs, while processing call data on your instructions with configurable retention and real-time deletion on request, so an erasure request takes minutes instead of a rebuild. Visit rednea to see how an AI phone assistant fits into a deletion workflow you can defend.

GDPR data deletionGDPR erasureright to erasuredata deletion requestsAI phone GDPR

Try rednea, no strings attached

AI phone assistant for business. Hear a live demo in your browser, book a call with our team, or get started — from £90/month, cancel monthly, no minimum term.

GDPR-compliant · EU & UK GDPR · Multilingual