VergeResources,
I'm not sure why you can't improve this with an index, may be it's down to your version/operating system etc, not allowing dates to be indexable. I know you can get in a right mess with your index structure using something like dates, as they don't spread evenly. What versions etc do you have.
As an interim soultion maybe you could define another table and insert the date in there each time you update your base table. The "new" table need only contain 1 record, saving your scans and diskspace putting the date on each row.
Just code along the lines
UDPATE TABLE
SET MY_DATE = Current Date
whenever you update the base table.
Not the most elegant solution, I admit. But it may get you out of your current problem, with minimal effort and investigation.
Cheers
Greg