This feature already exists. Go to the MSN Messenger contact window, right click a contact, go down to "Messenger Plus! Extras" and hit "Set Come-back message".
You should get a window similar to this:
But it will only let you do it for when they sign in.
You can set a custom notification to tell you when someone returns from being away, on the phone, out to lunch, etc.