New warning messages might as well be fatal errors
There's a widespread view that a good way of deprecating something is to have the new version of your project emit warning messages when it runs across code using whatever you're getting rid of. The theory goes that this is pretty harmless; the people using the to be removed feature will get notified about the situation but can fix their code at relative leisure, because things still work.
As a working Unix system administrator, allow me to disagree violently. To sysadmins, a program's output or its lack thereof is a vital part of its behavior; adding things to the output is anything but harmless, and often forces us to fix the program right away. Many times the program is effectively no longer working and you might as well have made the warnings be fatal errors instead.
In real life, a program's output is part of its interface, and thus adding 'harmless' deprecation warnings is changing the program's interface. Sometimes you will get lucky and no one will have been depending on that particular bit of the interface, but this is rare if your library, language, or whatever is at all popular, and it is generally out of your control (because it depends on what people have built with your project).
If you want to print deprecation warnings for something, the system administrators of the world will thank you if you make it not the default behavior. That way people who actually care can check when they want to (or run in checking mode all the time), but you won't cause pain for others.
(This applies several times over if you print the warning more than once. Especially if you do not rate limit the warnings.)
If you want to print deprecation warnings anyways you should treat them as the last step before removing the feature entirely, not the first step. In fact, you should treat the addition of the warning as the removal of the feature, and tell people to consider it an incidental bonus that some programs keep on working anyways. This should hopefully create the right mindset in all parties.
(If it forces you to slow down the feature removal, tough. That's what the schedule should have been to start with.)