Drupal - TrustedResponseRedirect failing - how to prevent cache metadata?

You mentioned the URL generator, which is one of the two ways this happens.

In short, you need to do something like my patch in this issue: https://www.drupal.org/node/2630808

Pass TRUE to toString(), then you get a different object back that you need to add as a cacheable dependency. You can do that with such GeneratedUrl objects, entity and config objects and you should do that whenever your response depends on them.