The amount of IM spam is growing steadily. Even if you can set up your email client to reject messages from unknown senders, still you have to look at request to add you as a friend, which are could be used as a spam media.
There is a very elegant solution to this problem. It is based on hashcash idea. Whenever somebody contacts you on IM first time his as part of handshake protocol he must invest some CPU time. Let us call your IM client a "server" and an IM client which attempts to connect to you a "client". Server presents a client with a challenge. Client does some calculations based on this challenge and sends back a response. The server then validates if response is correct, and only then shows the client's message to the you. If response is not correct, the message is silently discarded. The hash cash paper presents some examples of so-called "non-parallelizable cost functions" which could be used in interactive (challenge/response) mode.
Why wold it work? Spammers are making their money by volume. They send millions of messages. While it is not a problem for your desktop to invest few CPU cycles for each connection, for spammers this number will multiplies by millions of connections they are initiating and the required CPU resources will hopefully make their operation not profitable.
If you run your IM client in "friends-only" mode, this mechanism should be applied on "add friend" requests. People need to invest CPU time before you will see their "add friend" request. if you accept messages from anybody (not using "friends-only" mode), then this mechanism should be used on beginning on new conversation (first message). An example of similar mechanism was recently implemented as a plugin for Adium IM client. Their challenge-response mechanism is human-powered.
UPDATE: there is a Jabber Protocol Extension JEP-0158 which suggests to use hashcash.