Postgres Materialize causes poor performance in delete query
My guess is that at rows=524289 the memory buffer is filled up, so the subquery has to be materialized on the disk. Hence the dramatic increase in the time needed.
Here you can read more about configuring the memory buffers: http://www.postgresql.org/docs/9.1/static/runtime-config-resource.html
If you play with work_mem you will see the difference in the query behavior.
However using join in the subquery is much better way to speed the query, since you are limiting the number of the rows at the source itself vs simply selecting first XYZ rows and then performing checks.