I haven't read the whole thread, so apologies if this was suggested already. I think I got this idea here (well, actually Eric's site back during 3E's beginnings).
At first level, max as per usual. But after every level, you roll all of your hit dice, including your first level. If the total, including Con bonus, is higher than the previous total, you take it. If it was lower or equal to your old total, you take the old total plus 1.
Example: My lvl 1 Rogue with 10 Con has 6 hp. 2nd lvl, roll 2d6 and get a 8. So he has 8 hp at 2nd lvl. At 3rd, 3d6 gets him a 16, so his new hp total is 16. 4th, 4d6 he gets 15, so at 4th he has (16+1) 17. And so on.
It allows for randomness, decreases the chance of a low hit point total, allows a low roll to become a better one as levels are gained and makes it difficult to capitalize on a lucky roll for the life of the PC.