Insert With Common Table Expression - MySql

In the case you have a MySql table filled with default Lookup ids for each user in your system to a messsage id.  In this case you are looking to fill in the many to many relationships of bridging table from a User table to the Message table.

For simplicity sake something like this

This is an inherited structure so there are numerous queries and dependencies in the system so modifying the data structure is a large change.

I need to backfil for users to new particular message ids that will be available to all users except a few excepted users (because they are internal)

As there are vastly more users than messages the first part of adding messages is not a complicated step as it is a insert of direct values something like

INSERT INTO Message(Id)
VALUES
(123),
(456);

As I know I'm only insert 2 new message types in this example but let's say I have thousands or millions of users then I should do something like this

INSERT INTO UserMessageAssociation (UserId, MessageId)
WITH
    u as (
        SELECT 123 as MessageId, UserId
        From User
        WHERE Type NOT IN
        (
            1, -- System
            2  -- SupportAgent
        )
        UNION
        SELECT 456 as MessageId, UserId
        From User
        WHERE Type NOT IN
        (
            1, -- System
            2  -- SupportAgent
        )
    )
SELECT u.UserId,
       u.MessageId
from u;

The UNION is not great performance wise, but I want to make sure users are unique, the WITH common table expression builds out the implicit query results like a temp table would.