It's totally up to the individual, but if you can't contact your users directly, then I'd start by putting the shut down notice on your page with probably 3 mon

It's totally up to the individual, but if you can't contact your users directly, then I'd start by putting the shut down notice on your page with probably 3 months notice, as well as a warning that there will be a 24-72 hour outage in 30 days time, and another one in 2 months that would be closer to a week long. The outage should be long enough to cause major problems for people relying on it. The emails will come flooding in, turn the service back on, notify the users that contacted you, and they now have X months notice to get it fixed up. At least that way you can feel good that you put an honest effort into trying to notify your users. An update with two weeks notice on your website that the developers have long since forgotten just doesn't cut it.