Absolutely right.
If this is a commonly used query, I would probably "bite the bullet" and make sure there was an effective (i.e. time-saving) covering index and that SQL was actually using it for the query (it's easy to forget that step, but just because you know the covering index is there doesn't necessarily mean SQL will use it :-)).
If it's run once a month, say, you might just let this particular query be a little slow rather than adding an index to the table or otherwise enlarging the table.
Scott Pletcher, SQL Server MVP 2008-2010