Have you actually had the battery tested? Tested under load? Sounds to me like your battery isn't as good as you think it is.
If the battery is nice and good as new then I'd check out the starter. Make sure connections and grounds are good at the starter.
Keep us posted