How do I delete books from Purchased Books? I've tried to follow the steps you do to delete from other collections, but it doesn't work.

You should be able to delete downloaded books from your bookshelf via the Edit button at the top left of the shelf. But you can't currently permanently delete any items from your purchase history, all you can so is hide them so that they are less visible : hiding and unhiding. (hiding doesn't appear to work directly on iOS 6 devices, but you should still be able to hide them via your computer's iTunes).