As any other software system, frameworks and libraries evolve over time, and so their APIs. Consequently, client systems should be updated to benefit from improved APIs. To facilitate this task and preserve backward compatibility, API elements should always be deprecated with clear replacement messages. However, in practice, there are evidences that API elements are usually deprecated without such messages. In this paper, we study a set of questions regarding the adoption of deprecation messages. Our goal is twofold: to measure the usage of deprecation messages and to investigate whether a tool is needed to recommend such messages. Thus, we verify (i) the frequency of deprecated elements with replacement messages, (ii) the impact of software evolution on such frequency, and (iii) the characteristics of systems which deprecate API elements in a correct way. Our large-scale analysis on 661 real-world Java systems shows that (i) 64% of the API elements are deprecated with replacement messages per system, (ii) there is almost no major effort to improve deprecation messages over time, and (iii) systems that deprecated API elements in a correct way are statistically significantly different from the ones that do not in terms of size and developing community. As a result, we provide the basis for the design of a tool to support client developers on detecting missing deprecation messages.