I know exactly how to handle this as I did it before and it worked really well.
1. Make sure the feature can be completely hidden from the UI.
2. Add an option somewhere in Advanced section of Preferences that toggles the visibility of the feature.
3. Turn the feature off for all new users and keep it on for all existing ones.
4. If it is possible to detect whether the feature is used by an existing user, then if it is not used, show one-time message saying the feature is being turned off and how to turn it back on if needed.
When do you remove the feature entirely? Or do you just discourage users until, at some future point when a change breaks it, you don't get any complaints?
1. Make sure the feature can be completely hidden from the UI.
2. Add an option somewhere in Advanced section of Preferences that toggles the visibility of the feature.
3. Turn the feature off for all new users and keep it on for all existing ones.
4. If it is possible to detect whether the feature is used by an existing user, then if it is not used, show one-time message saying the feature is being turned off and how to turn it back on if needed.
That is it. Graceful deprecation.