It sounds like the original poster has already effectively, but informally deprecated their API (anything that is referred to as 'old API'). However, until it is announced and users are notified that an API is deprecated, it is not formally deprecated.
Deprecated API is an interim, inactive stage of code. It is the last rites. This is the period that allows adopters/consumers to reconfigure their apps for a newer API and bid a fond farewell, making peace with the API. Some APIs may linger longer than others, but at this point we know their time isn't long.
Deleted API is a code funeral. There is nothing more that it can do, but properly disposed and appropriately memorialized.
Many API and service developers opt for code funerals rather than performing last rites; however, I think that is somewhat risky. If there was any kind of service or support promise made when the API/service was either initially adopted or through renewal, you may want want to honor that committment for a reasonable period of time before performing the funeral.
For non service libraries, I think one major release version, regardless of the period of time, is probably a more than acceptable and fair period of guaranteed backwards compatibility. Beyond that it depends on the influence and lobbying by users to extend it's life beyond that period. And don't be suprised if from time to time there are objections due to irreplacable 3rd party dependancies being stuck in limbo, and tied to certain versions of certain platforms.
For services, I suspect you might want to look at either a six month or year period, simply because of the variance in by who and by how a service can be consumed, and the corresponding development cycle variance from consuming project to consuming project -- many projects that might be consuming your service could still big up-front design, and may schedule a release cycle of longer than a year. Most developer opinions from the outside would suggest that those with long schedules are responsible for meeting your cycle times, and those long cycle consuming projects should adopt a quicker release cycle, and it may be true. But ultimately the date of deletion is something that you have to negotiate with users.
A good but not bulletproof strategy for deprecation might be when annoucing deprecation, highlight the timeframe for intent to delete, along with a request for comment or objection in a survey format of the API sections in question. If you don't have a contact list of users because your service operates with [semi] anonymous access, you might consider looking at logs for frequent and active users and dispatch the notification to the host or domain administrator to forward as they see fit.