My solution
My battery IS definitely improving, I've done a complete cycle sometime this week, and often charge at night when the battery gets down to 25-30%, and allow it to stay long enough for trickle and top-off charges.
I've done it all, except for restoring. I went to the Apple Store, battery checked out okay. I turned off iCloud cellular documents, re-did iCloud after hard reboots, including my mail accounts, set the mail settings to manual, use Siri minimally, turned off several location settings, deleted the Facebook app for sometime (that proved better battery life), turned off Stocks Widget, turned Wi-Fi off outside of the house, brightness to 50% auto, Bluetooth, Wifi-Sync, and Ping OFF, system location settings off, you name it.
Like before, my battery is improving. I just think it takes a couple cycles for the Lithium-Ion battery to reach its full potential, like I've had with my 2nd gen iPod Touch, which SUCKED when I got it, and now lasts about 2 weeks on standby.
I'm easily getting about 30 to 35 hours of both usage and standby combined on one single nightly charge. Compared to about only 4 hours of usage, with 12 hours of standby when I first got the phone.
If this doesn't help, then just wait for iOS 5.1 or return the phones. I'm becoming very pleased with my phone, I'm starting to get 'reasonable' times. Just be patient.
The pictures below are my difference in battery.
The first (left) is after my first complete discharge, minutes before the phone died.
The second (right) is tonight, at 18%, minus about 30 to 40 minutes standby from charging.
-William