Mysql Inner join performance
The first query will be faster this way:

select * from `entries` 
    where EXISTS (
        select * from `users` where `entries`.`profile_id` = `users`.`id`
                 ) 
order by `id` desc


It needs an index (PRIMARY KEY?) on users.id.  It is faster because the subquery quits when finds one row, rather than counting all of them.

The query part cannot use that technique.  But I think it is much simpler than what you have:

SELECT  e.*
    FROM  
      ( SELECT  user_id
            FROM  `tag_user`
            WHERE  tag_id IN (119, 36)
            GROUP BY  user_id
            HAVING  count(*) = 2 
      ) x
    JOIN  entries AS e  ON e.profile_id = x.user_id 


Notice that users does not seem to be of any use.

entries will need INDEX(profile_id).

I assume tag_user is a many-to-many mapping table?  Have you followed all the advice in this?  The advice there may provide further performance boost.

If you need to discuss this further, please provide SHOW CREATE TABLE.