OP, I bet your coolant being warm-ish actually keeps your engine bay a few degrees warmer. That along with the engine turning over like a champ and the fuel igniting easier (warm engine = less compression to ignite), probably just makes it feel like the batteries are charged.
I had a similar issue when my alternator was going out on me. Swapped it, and I've been good ever since. My dying alternator would slowly drain my batteries when the truck wasn't running, so if it sat for a couple weeks, it wouldn't want to start.
Another good trick an old timer taught me is to toss a light bulb next to your battery. Run a splitter out at the truck so when you plug it in, you are plugging in an old light bulb sitting next to your batteries. The little bit of heat from the light will do more good than you think. I only had to do that at subzero temps though.
Finally, get some good batteries. I picked up the biggest Red Top Optima's they had back in summer of 2008 and they have been drained dead more than a few times by me and are still great. Not as good as they were brand new, but still great.
unless the PO added a battery minder to the block heater plug in (I actually like that idea)
I really like this idea too... I doubt a small motorcycle sized one would do anything with around 1800CCA worth of batteries though, and I assume most use a timer so their trucks aren't heating coolant all night.