Retrieving data speed tweaks SQL Server 2005
Your table is a "heap," which means that it doesn't have a clustered index.  The short version of what that means is that your data isn't laid out on the disk in a logical way.  A heap really isn't an optimal structure for an actively updated table.  Here's an excellent video on heaps.

So, my suggestions--please test them before deploying them in production--are:

BEGIN TRANSACTION

USE fp; ALTER TABLE fp_core ADD ID bigint NOT NULL IDENTITY (1, 1)
GO

USE fp; CREATE CLUSTERED INDEX IX_fp ON fp_core (ID) WITH (STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

COMMIT


This will take some time to complete AND will be a blocking query, so do it during downtime.  

This will give you a clustered index and lay out your table on a completely random sequential number, unfortunately, but since you don't have any non-unique values that might be the best course of action.  

I would then include the columns note_id and timeoffset in your nonclustered index on HASHKEY.  

BEGIN TRANSACTION

USE [fp]
GO

IF  EXISTS (SELECT * FROM sys.indexes WHERE object_id = OBJECT_ID(N'[dbo].[fp_core]') AND name = N'IX_Agency_TIMESTAMP')
DROP INDEX [IX_fp_core] ON [dbo].[fp_core] WITH ( ONLINE = OFF )
GO

USE [fp]
GO

CREATE NONCLUSTERED INDEX [IX_fp_core] ON [dbo].[fp_core] 
(
    [hashkey] ASC
)
INCLUDE ( [note_id],[timeoffset])
WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON, FILLFACTOR = 80) ON [PRIMARY]
GO

COMMIT


(Or you could do it through the GUI.  If you right-click on the index and choose properties, there's an included columns pane.)  

This will hopefully have the effect of replacing your heap scans with nonclustered index seeks, but since your query has a "where in [30,000 items], it might do a index scan instead.  Either way, it won't be rooting around in the heap, which I expect will be a good thing.