Scaleable Asynchronous Grouping + Sorting

Question

Problem: Process messages asynchronously in a scaleable fashion, where each message belongs to a group and the messages in a group should be processed in order.

My thoughts (could be a completely wrong solution): Initial scenario: I have messages coming in from a message queue, for each message I generate a key. For each key, I have a consumer that processes the messages in order of the timestamp.

Messages:

Timestamp1 - Message1 - Key1
Timestamp2 - Message2 - Key2
Timestamp3 - Message3 - Key3
Timestamp4 - Message4 - Key1
Timestamp5 - Message5 - Key3

So Consumer1 processes messages with Key1, Consumer2 processes Key2, etc...

My problem is that if I want to add a new Consumer to scale the solution, that could cause the messages to change key, so something that previously was Key1 could move to any other Key (could be multiple different keys for multiple messages that were in Key1 previously). The only thing I can think of is to wait for all the previous messages to be processed and then scale the solution with the new key.

Is there any good algorithm that could help with my solution or the original problem?