The key word here is **"relational division"**.

For the given specifications, it won't get faster than this::

~~~pgsql
SELECT package_id
FROM   package_to_message p1
JOIN   package_to_message p2 USING (package_id)
JOIN   package_to_message p3 USING (package_id)
WHERE  p1.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_1')
AND    p2.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_2')
AND    p3.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_3')
AND    NOT EXISTS (  -- no other!
   SELECT FROM package_to_message p0
   WHERE  p0.package_id = p1.package_id
   AND    p0.message_id NOT IN (p1.message_id, p2.message_id, p3.message_id)
   );
~~~

But maybe you need a more generic/dynamic query ...

~~~pgsql
PREPARE q1(text[]) AS
SELECT p.package_id
FROM   message m
JOIN   package_to_message p ON p.message_id = m.id
WHERE  m.name = ANY($1)
GROUP  BY 1
HAVING count(*) = cardinality($1);
~~~

Call:

    EXECUTE q1('{message_name_1, message_name_2, message_name_3}');

Related:

- [How to filter SQL results in a has-many-through relation][1]
- [Using same column multiple times in WHERE clause][2]
- https://dba.stackexchange.com/questions/194269/arbitrary-queries-on-nm-relationship-including-all-and-any/194333#194333

  [1]: https://stackoverflow.com/a/7774879/939860
  [2]: https://stackoverflow.com/a/47512013/939860