It sounds strange yea, but the battery should have no effect on phone going into deep sleep since they battery does not control functions of the phone except for NFC. If you have an aftermarket battery (non-samsung) then it could possibly be problems with NFC. Most non OEM batteries don't support NFC so you should disable the feature in your settings. If you battery does support it then you should be okay. I am not saying this is your problem but its something to check into.
Aside from that, the battery really has no effect on what you phone does or doesn't do, aside from the obvious power source. Let GSAM Battery Monitor run for a little bit and post a screen shot of what it says. If an app is running rogue than that should be close to the top if not the first thing that would appear on the list.
Next question I should ask is are you running stock, or are you unlocked/rooted running a custom ROM?