Why might a table scan have a huge I/O Cost?
As per the comments:

See SQL Server “empty table” is slow after deleting all (12 million) records – Remus Rusanu

The answer to this question is: Ghosted Records, subsequently confirmed by the original poster. Posting here for completeness.