Decent people can disagree in good faith regarding how to apply a law
I would apply the "purpose limitation" to reach the opposite conclusion of @user672.
This is despite the fact that I agree with that answer's statement of the pertinent provisions of the GDPR, and despite the fact that I agree that the answer is well reasoned. I could see either interpretation prevailing in the event that the issue was adjudicated.
Often even when people agree on what the law says, there is more than one well reasoned conclusion that can be reached about how to apply the law to the facts, which is why lawyers need to exist even in an ideal world where everyone is honest and everyone tries to write clear laws and everyone is acting in good faith.
The law is full of gray areas like this one where there is no definitive resolution to the true answer until a dispute presents itself and is resolved (something that may never happen in low stakes disputes like this one).
My Contrary Analysis
My Purpose Analysis
I would begin by concluding that company is retaining information for the "purpose" of providing good customer service (e.g. so the client can easily reorder the pizza via an app), and the legal name of the road is irrelevant to that purpose if it makes the customer happy.
So, what the customer says is fine in my view.
My Storage Limitation Analysis
With regard to the "storage limitation", reasons to keep the information could be to facilitate reordering pizza via an app, in the event of a credit card charge dispute, in case of a health recall, for a sales tax/VAT tax audit, or for managerial economic reasons (e.g. to decide where delivery service should be offered in the future based upon distance and sales volume, or to divvy up territories among delivery employees equitably).
Of course, the "storage limitation" issue can't really be resolved until we know how long and in what way the information is retained.
For example, the credit card chargeback information is only a justification to retain the data until a chargeback is no longer possible.
Similarly, a managerial economic reason to retain the data may justify only the retention of the data in a way that is not personally identifiable without additional detective work. For those purposes, it doesn't matter if the pizza was purchased by the current tenant of that address or the person who lived there before him.
Interpreting Statutes And Regulations In Light Of Their Purpose
I would also be swayed in how I apply the accuracy requirement of the GDPR in the context of its statutory purpose which is to protect the privacy of people who deal with the data maintainer for the purpose of benefitting the people entitled to privacy protection.
Usually evaluating whether something violates the law in terms of the potential consequences of doing so if there was ever a dispute is a helpful exercise.
The purpose of the GDPR is not primarily to make information stored in databases more accurate because accuracy in data collection is a value that the GDPR itself exists to promote. The accuracy requirement in the GDPR exists for the purpose of furthering "consumer" privacy and protection. Certainly, the GDPR doesn't make accuracy a goal that must be pursued at any cost in situations when accuracy is only materially material.
There are lots of contexts in which inaccurate data collection can impair privacy. For example, if a "Jr." is listed as a "Sr." in a name field, or the "Jr." or "Sr." affix is omitted when it is part of a name that could cause the wrong people to gain access to that data.
For example, creditors of "Jr." doing a credit check might gain access to information that is really information that belongs to "Sr." which "Jr." doesn't have the authority to let prospective lenders to him see. Also, if undiscovered, the error could harm "Jr." if "Sr." has worse credit than "Jr." does.
On the other hand, a dated street name is unlikely to compromise the privacy of the pizza customer, and the customer has already directly expressed an opinion regarding his interpretation of his best interests in the matter.
Certainly, the pizza customer could never file a valid complaint if the pizza company entered his address in their database as he intentionally directed them to do (even if it caused his pizza to be delivered later repeatedly) in this situation, and no one else but him should have any standing to file a complaint or seek a remedy regarding the accuracy of data related to him under the GDPR.
There wouldn't be a GDPR accuracy claim for a third-party, even if someone had standing for some other reason such as in connection with a breach of contract suit or misrepresentation suit in the face of a contractual representation that the existing data was accurate made to someone using the data for some purpose other than pizza delivery, with proper consent from the person about whom the data was collected.
Standard of Review
Another issue in the case of regulatory type legal regimes like the GDPR is how much leeway someone applying the regime should be given before it is considered a violation.
Often when a regime like this one is applied, the standard for determining if there is a violation is that the GDPR requirements were applied unreasonably, or that the person implementing them abused their discretion in applying them to their data collection regime, rather than merely determining like an umpire that the application was right or wrong in the abstract.
There isn't enough experience applying the GDPR yet in practice to really know whether people enforcing it will afford data collectors a fair amount of leeway for multiple reasonable applications of the GDPR to their own situations (in which case any consistent approach taken by the pizza company as a conscious matter of policy might be upheld), or if it will be applied strictly according to the enforcement body's views without any recognition that a certain amount of discretion should be allowed to data collectors in applying the GDPR in practice, at least until further guidance for particular issues is promulgated publicly.
By analogy, in areas of tax law where no one accounting practice is prescribed and a company applies the tax laws in a consistent manner (e.g. deciding when to treat money paid towards a loan as interest v. principal payments when the loan documents are unclear), this will normally not be considered a tax law violation no matter which rule is ultimately adopted by the company.