Slow query when adding additional where clause
@Joishi already provided an explanation for what you saw.

Here is a solution to make it fast.

Your query (unchanged) after trimming some noise:

SELECT m.*
FROM   posts    p
JOIN   messages m ON m.post_id = p.id
WHERE  p.project_id = '418fdd03-ab90-4efd-b04d-5d5563d58972'
AND    m.kind = ANY ('{10,11,12}')
ORDER  BY m.updated_at DESC
LIMIT  100
OFFSET 0;

1. Multicolumn index on posts

This is only a minor improvement and not strictly necessary. Should give you an Index Only Scan instead of an Index Scan. Saves the lookup on the heap (the table)

 CREATE UNIQUE INDEX index_posts ON posts (project_id, id);


UNIQUE is also not necessary, but it better documents that the index is, in fact, unique.

2. Partial multicolumn index on messages done right

This is the major part.


Use the same predicate in the partial index and in the query. Postgres only applies very rudimentary tests to determine whether an partial index is applicable. Else, the cost would get out of hand quickly.
Since kind IN (10, 11, 12) is rewritten to kind = ANY ('{10,11,12}'::integer[]) internally, it should still work in this case, but it's better to be clear.
It would be useless to make kind the indexed column here. It's only relevant in the predicate, not as column to retrieve from the index. You need an equality check on post_id (so it comes first) and a range check on  updated_at (so it comes after that). Details:


Multicolumn index and performance


DESC is not strictly necessary, but still better here.


-- DROP INDEX index_messages_on_kind;
CREATE INDEX index_messages_on_kind ON messages (post_id, updated_at DESC)
WHERE kind = ANY ('{10,11,12}');

Then run ANALYZE on both tables and try EXPLAIN ANALYZE again. Are we fast, yet?