> If that's right than handling a GDPR data request 100% according to the rules would require having some way to search nearly every computer we've got looking for anything concerning any particular customer.

You’re only half right. If you habitually store data and never delete it from those stores, yes, you have to find and provide it. If they’re temporary (voicemail, fixing a specific issue) and you remove it as soon as it’s no longer needed, you’ll be fine.

> It included a vast amount of things that the company had inferred from the data.

If you’ve tied it to that person, it’s in scope. It’s literally part of GDPR.

> Customer service rep sends an email to their supervisor saying the customer won't take reasonable advice and then gets abusive and asking the supervisor how to deal with future calls from them?

Possibly but you could argue not because that could be business risk.

> I make a list on my computer of customers that I think are exploiting a bug in our billing system to get a lower price, print out that list and assign it to someone to investigate and fix the bug if it exists.

No, you have a valid reason to not share that, as long as you remove the PII once you’re done.

> leaves a voice mail where they include "my new credit card number is <xxx> with security code <yyy> and expiration date <zzz>", that's supposed to show up in their GDPR data.

If you’re deleting voicemails as you address them you’re fine, you won’t need to include this just because you didn’t get round to deleting it yet.