Try the duracell ultra or some specificaly designed for paintball, can't remember what there are called but Planet Eclipse sell a pack of 2 for about £4, there the same as you get in New Eclipse markers and so far I've found them to be very reliable.
It does seem the normal 9v Duracell's are not what they used to be, it could be the weather but they dont feel as heavy as they used to so it gives the impression theres less inside them.