Be careful with AF fine tune. You can only set one value for the lens, so only use it if your lens consistently front focuses or back focuses at all focus distances and all zoom settings.
I think you should try single-point AF-S first. It won't let you shoot unless the camera thinks you're in focus. If those shots come out incorrectly focused then you may well have a focus accuracy problem. Otherwise, since you say you heard the focus motor while recomposing, my guess is that AF-A is engaging one of the focus tracking modes and it isn't tracking quite as reliably as you might wish.
I have been training myself to use back-button focusing, and in that exercise I thought it might be clever to use 9-point AF-C (a tracking mode) to account for any jitters or slight motions by me. Results prove me wrong: dialing down to single-point, whether AF-S or AF-C, seems to deliver more reliable results in my hands. The multi-point mode seems to like to jump between AF points a little too eagerly.