I've found the Lithiums that come with the mouse are quite good. They'll last a month plus some change. Duracells, maybe 2-3 weeks.
Right now I have some Monster Battery rechargables, enough so that a pair is always sitting in the charger. This is the best solution I've found so far.