Use factory pattern with single and multiple returns

I have a factory pattern implemented for handling several messages which derive from the class MessageBase (e.g. StartMessage, etc).

To handle these messages, I have different handlers that derive from IMessageHandler:

public interface IMessageHandler
{
      MessageHandleResult HandleMessage(MessageBase message);
}

public class StartMessageHandler: IMessageHandler
{
      public MessageHandleResult IMessageHandler.HandleMessage(MessageBase message)
      {
         ...
      }
}

To retrieve the handlers, it is quite simple:

var messagehandler = MessageHandlerFactory.GetMessageHandlerFor(message);
var result = messagehandler.HandleMessage(message);

But in the new situation, I have to handle a new type of message (which also neatly derives from MessageBase). The messagehandler for this new message must return the result as a list of messageresults:

public class NewMessageHandler: IMessageHandler
{
      public List<MessageHandleResult> IMessageHandler.HandleMessage(MessageBase message)
      {
         ...
      }
}

Any ideas on how to refactor this in a correct way. The solution was working perfectly for 6 types of messages until this new message type was introduced.