When you make the decision to lower the price of a product, how do you address that change with existing customers (those who have paid the higher price)?

If you're lowering your price, you might have bigger problem than how to communicate the change. This sounds like a more fundamental product strategy, positioning, and segmentation question than it is about pricing.

In general, communicating price changes (higher or lower) and determining eligibility isn't the job of the pricing function. It's pricing's job to make a recommendation that supports the company's strategy and helps hit financial targets. Ultimately, it will be up to customer-facing teams to execute against the change.

As part of our monetization strategy, we developed a set of principles that define not only how we price, but how we implement and managing various situations. They include ideas such as fairness, flexibility, predictability, comprehension, durability, and customer-focus. Within these you can define migration principles that will help you navigate these situations as they arise.

I like to start from a place of trust: give customers a credit for the difference.

Think about how much more likely you are to come back to a restaurant who made a mistake on the order and gave you a free item to make up for it. 

You're playing a customer-lifetime-value game, not a maximize-one-time-revenue game. 

I've always taken the approach that you don't touch existing customers until at least renewal time. So if you lower your pricing there is no need to address your current customers until they come up for renewal. When they do come up for renewal, you may have to minimize your year over year price increases for those existing customers until they get closer to the average selling price of those customers on the new, lower pricing. If you publish your pricing and the current customers can see that and complain, you may need to supplement the product pricing with value adds like additional training sessions, preferential support options for those existing customers, free services etc until you can give them enough perceived value that leaving their product price the same won't cause them concern. I would try to avoid product price compression on renewals as much as possible though.