INNER JOIN making COUNT(*) slow
If the foreign key is not nullable, then there is no reason for the join at all, is there? So why not let SQL Server scan the most efficient index available instead of computing a join that will result in the exact same count?

SELECT COUNT(*) FROM dbo.messages;


That said, you can do this much more efficiently:

SELECT SUM(rows) FROM sys.partitions
  WHERE [object_id] = OBJECT_ID('dbo.messages')
  AND index_id IN (0,1);


This will be slightly inaccurate due to in-flight transactions, but it also won't block (or be blocked by) any activity against the table, so pick your poison.