I've been racking my brain trying to think of the first service that I used regularly that was shut down. Pownce maybe? (anyone else remember that?).
I'm currently hunting for a replacement for Gmail that is self-hosted, or at least a solution where the cost of switching providers is low (i.e. I could shift my email to a new host without changing my email address or losing my message history). I'll probably end up using some sort of IMAP provider. There are a lot of features I'd stand to lose though. Conversation view is hugely useful, and Gmail's spam filter is just unbeatable.