I went to the US last fall and due to sheer sloppiness I managed to stay 1 day too long (September 2 through December 1). Here is my confusion. It still says that my ESTA application is valid. Does that mean I am eligible to re-enter? If not, if I re-apply for an ESTA and it is approved, does that mean I'm eligible to re-enter? Or is it possible that my ESTA is approved and I'm still denied entry at the border?
It it indeed possible to have a current ESTA approval and still be rejected at the border. The border is always where the actual entry determination is made; ESTA itself just authorizes the airline to fly you to a port of entry so you can apply for admission there.
In fact, given that you have overstayed a VWP visit once, the rules as written say that you must be rejected if you try to enter under the Visa Waiver Program ever again. I suppose it is possible in practice for a border guard to bend the rules for you, but I wouldn't count on that happening at all.
You will need to apply for a visa if you want to visit the US again.