No, it wasn't all that expensive in the end though a fair amount of data was kept around. I did it for forums, not file-storage and coincidently I've been wanting to resurrect it for forums and have thought about it for file storage, too.
The datamodel I used to implement this for ACES forums would work for tracking "new" for OpenACS forums, at least the strategy would work. I think it should be parameterizable by forums package instance. I think for ACES I may've made it parameterizable by forum.
I've not looked at what it would take to do this for file storage.
And of course the holy grail would be a generalized service that could flag any unread content of any type heh heh heh.
As you know from earlier e-mail I'm all in favor of supressing the timestamp for folders if that makes things less confusing for users.
But I think you're on the right track with the idea of making "new" useful.