This should be incredibly faster:

SELECT StatusName PNRStatus from dbo.Status S

WHERE EXISTS (SELECT * FROM [Transactions] T WHERE T.[PNRStatus]=S.StatusName)

ORDER BY PNRStatus

SELECT [AgentID] from dbo.Agent A

WHERE EXISTS (SELECT * FROM [Transactions] T WHERE T.[AgentID]=A.[AgentID])

ORDER BY [AgentID]

SELECT StatusName ScriptResult from dbo.Status S

WHERE EXISTS (SELECT * FROM [Transactions] T WHERE T.[ScriptResult]=S.StatusName)

ORDER BY ScriptResult