PD_ALL_VISIBLE flag set - autovacuum ignoring dead tuples

I'm seeing a heavy-update TOAST table which is not being effectively autovacuum'd on 8.4.5. The stats collector shows n_dead_tup growing very quickly, and autovacuum runs frequently, but never removes any dead tuples. A manual vacuum does find many dead tuples (90+ % of the table) to remove, and removes them properly.

Whilst debugging, I found that there seems to be a large amount of the old 'PD_ALL_VISIBLE incorrectly set...' warnings emitted during the autovacuum run.

My immediate assumption was that PD_ALL_VISIBLE is set on the page, and so autovacuum skips it. However, from what I can see in lazy_scan_heap(), all of the clean-up actually happens before we even check the PD_ALL_VISIBLE flag and emit this warning. Can anyone confirm that this is a warning message only, and shouldn't actually cause autovacuum to skip pruning dead tuples?

Am I seeing two different or related issues here?

Thanks,
Tom

p.s. I'm aware there was a change to PD_ALL_VISIBLE in 8.4.8 but that was to stop warning on a non-issue, so I don't believe it's the same.