Why are you at exposure + 2/3? It looks plenty exposed, and I don't think you need that. This would give you back 2/3 of a stop more speed.
Was it really dark out when you took these? ISO 800, 1/1800th of a second and f/5.6 is 3 whole stops more light than the sunny 16 rule would suggest on a sunny day (and you're not shooting anything very white or black). Even when you add back your exposure compensation, that's 2.3 stops higher. If it was cloudy or something (I don't see any shadows on the water, but they may have been cropped), then try shooting on a nice bright sunny day, which might give you even more speed.
Add both of those together and you could easily be shooting at 1/4000th of a second instead of 1/800th, which may be enough to stop the blur.
Also, are you panning your camera to track the bird? it doesn't matter if you're shooting at 1/1000th of a second or more, panning your camera so that the subject stays in the middle of the viewfinder as you shoot will make it slow down relative to your shot and make it easier to get crisp images. Takes practice.
Finally, if your lens doesn't have VR, then that will make you more prone to blur. VR won't help much with horizontal movement of a subject, but it would help you to pan better in horizontal stabilization mdoe, which eliminates some of your vertical hand shake while panning.
edit: oh also I read in a couple places about people who mounted red dot rifle scopes on their hot shoes lines up with the center of their viewfinder, to allow them to get the bird in frame in less than a second once noticed. Gives you more time for focusing and more chances to shoot. I don't know if this really helps or not, but it was interesting.