Here is yet another way to tackle this.

If an article is voted for first the first time after time X of not being voted for, it goes back on the new page as of the time of that vote. I don't know the aging algorithm that is used on the main page, but make it be one where the age of the article doesn't matter, but the age of the votes for it do.

This would also handle the case where someone dives through the new submissions page and votes for an article that was posted several hours ago.