It's not entirely clear whether you're trying to optimize for depth-first or breadth-first search; the question suggests depth-first, but the comments at the end are about breadth-first.
You have all the indexes you need for depth-first (just index the hierarchyid column). For breadth-first, it's not enough just to create the computed level column, you have to index it too:
ALTER TABLE Message
ADD [Level] AS MessageID.GetLevel()
CREATE INDEX IX_Message_BreadthFirst
ON Message (Level, MessageID)
INCLUDE (...)
(Note that for non-clustered indexes you'll most likely need the INCLUDE - otherwise, SQL Server may resort to doing a clustered index scan instead.)
Now, if you're trying to find all ancestors of a node, you want to take a slightly different tack. You can make these searches lightning-fast, because - and here's what's cool about hierarchyid - each node already "contains" all of its ancestors.
I use a CLR function to make this as fast as possible, but you can do it with a recursive CTE:
CREATE FUNCTION dbo.GetAncestors
(
@h hierarchyid
)
RETURNS TABLE
AS RETURN
WITH Hierarchy_CTE AS
(
SELECT @h AS id
UNION ALL
SELECT h.id.GetAncestor(1)
FROM Hierarchy_CTE h
WHERE h.id <> hierarchyid::GetRoot()
)
SELECT id FROM Hierarchy_CTE
Now, to get all of the ancestors and descendants, use it like this:
DECLARE @MessageID hierarchyID /* passed in from application */
SELECT m.MessageID, m.MessageComment
FROM Message as m
WHERE m.MessageId.IsDescendantOf(@MessageID) = 1
OR m.MessageId IN (SELECT id FROM dbo.GetAncestors(@MessageID.GetAncestor(1)))
ORDER BY m.MessageID
Try it out - this should solve your performance problems.