If you see a straightforward way, please submit a patch!
Will do that.
Here is a patch which implements this. The PD_ALL_VISIBLE flag is set if all tuples in the page are visible to all transactions and there are no DEAD line pointers in the page. The second check is required so that VACUUM takes up the page. We could slightly distinguish the two cases (one where the page requires vacuuming only because of DEAD line pointers and the other where the page-tuples do not require any visibility checks), but I thought its not worth the complexity.
