In addition to this, mark them clearly as out-of-stock - fade out the preview image and prepend [out of stock] to the item description.

Ideally make it a choice - I don't like it when I order by price and it's overriden to (availability, price) - maybe it's out of stock because the price is that good, and I'm willing to wait.

and if you don't make that clear, I scroll through a bunch of useless results. I can't remember a single time when I wanted out of stock items shown by default.