The problem is that you CAN'T delete the shelves from the Touch! If I could, I would have done so. All that happens is that the books are deleted from the shelf (as well as the books on all the duplicated shelves) but the shelf itself cannot be deleted.
I am guessing that syncing the Touch and the iPhone is done via Cloud or similar, and not each other, if that makes sense? So I am unable to see that the two devices would be out of sync as they are not connected in any way.
I do so appreciate your taking the time to keep trying to sort this problem.