Consultas de MySQL UNION 2 que contienen ORDER BY

Esta es tu solución:

SELECT *
FROM
(
    **(**
        SELECT profileId
        FROM 
        (
            SELECT profileId
            FROM profile profile2
            WHERE profile2.profilePublishDate <= Now()
            ORDER BY profile2.profilePublishDate DESC
            LIMIT 0,40
        ) AS profile1
        ORDER BY RAND()
        LIMIT 0,20
    **)**
    UNION
    (
        SELECT profileId
        FROM profile profile4
        WHERE profileId NOT IN (
            SELECT profileId
            FROM profile profile4
            WHERE profile4.profilePublishDate <= Now()
            ORDER BY profile4.profilePublishDate DESC
            LIMIT 0,40
            )
        ORDER BY RAND()    
        LIMIT 0,40
    )
) TEMP
ORDER BY RAND();

Los cambios que he hecho son:

1. cada una de sus consultas que son parte de UNION debe estar entre corchetes (se muestra en negrita para la primera consulta; la segunda ya está encerrada)
2. eliminó el alias profile3 para su segunda consulta
3. para el ORDER BY RAND() final , debe crear el conjunto de resultados UNION en una tabla derivada; Le he dado TEMP como el alias

No he probado la consulta anterior, pero espero que funcione. Déjame saber tus hallazgos.