After extending the worldborder and using worldborder fill my world looks like this around the border: http://prntscr.com/fp450j

Is there any way to fix this?

All of those chunks seem to be properly generated, some just appear to have been generated with a different world generator. That can happen sometimes from bringing an old world to a newer Minecraft version if they've made changes to world generation since the version it was previously on. It can also happen if you are using different plugins/mods which make changes to world generation.

As for the apparent randomness to the pattern, I assume that's down to how Minecraft can sometimes generate distant chunks in a somewhat random pattern around the edges when it's under very heavy stress, such as when the world is first generating.

WorldBorder itself doesn't do anything to affect what world generator is used, it simply makes CraftBukkit (and by extension the Minecraft server) generate the necessary world chunks.

You can try Trimming the affected areas and then running Fill again to make those chunks consistent with each other at least, but if (as it seems) a different world generation process is being used now than was originally used on the world, the newly generated area still won't line up with the rest of your world.
Still, might be worth a shot, of course only after having backed up your world.

As you can see on our dynmap, close to the border you see black squares. Within the area of black squares, those chunk corruptions appear in-game. (http://prntscr.com/fpavxc)

Would it improve things if I follow this procedure:

Make the border smaller by 2,500.
Run the worldborder trim command.
Make the border bigger by 2,500.
Run the worldborder fill command.

Would I need to do anything with the dynmap too?

Hoping for a reply. @Brettflan

The map was originally generated on 1.9, extended on 1.11 and ran another worldborder fill. I don't have any other plugins then Worldborder/Dynmap that renders. If I were to extend it again in the future and run another worldborder fill the result would be the same? I don't feel like resetting my world due to this.. but kinda looks like I have to in the nearby future.

@Brettflan So I reset my world and doing a clean /wb fill now, however some of my forests have squares (not black) and the trees are cut in half. Is that normal?

Image: http://prntscr.com/fu001n

Hmm, I see that the chunks nearest the border seem to be properly fully generated, so you may be on to something.

How much memory is allocated to your server process, out of curiosity?

One further thing that could help ensure that it runs as smoothly as possible would be to disable DynMap's rendering process until Fill has finished, to keep it from having to devote memory and processing power to both generating the world and having DynMap render it at the same time. Normally that's not a problem at low Fill frequencies on most servers, but it does impact performance.

By the way, you might try visiting one of those chunks which is not fully generated and is missing trees and such, to see if it generates fully when you get near.

That's not normal, no. It looks like some of those chunks weren't fully generated, which shouldn't happen using Fill since adjacent chunks are kept briefly loaded to trigger proper full world generation for each chunk. If a single chunk is loaded without a few adjacent ones also loaded, the second part of the generation process which adds various features doesn't trigger.
I'm not sure why that would happen during a Fill, beyond possibly being caused by CraftBukkit/Minecraft getting overloaded in some fashion and for some reason deciding to unload chunks before it should do so (they're set in an unload queue to be unloaded when it's safe to do so).

Are you running at or near the default Fill frequency, or a lot higher? Is the process frequently causing the server to run low on memory? Mind you I haven't seen that happen even in those circumstances, but those are the only things I can think of which seem like they could possibly have some bearing on it.

EDIT:
I should mention, as covered elsewhere, setting a really high Fill frequency can sometimes cause various other problems beyond just making the process actually run slower, such as potentially causing the server to crash or freeze if it has a very low memory cap, which is why it is strongly discouraged. So this could possibly be another potential side effect with some versions of CraftBukkit.

I had it on default fill frequency, after that I switched to 1000 with 0 players being online. Since the server went low on memory really quick, I restarted the server, cancelled the fill process and restarted it on 500 frequency, same result. So I restarted it again, cancelled the fill process and put it on default frequency again. After 2 hours it started to give me errors because the memory was empty and at that moment I restarted the server again.

Playing with that might have ruined it?

Currently it's rendering on default frequency: http://mc.villagercraft.nl:8050

If I let it render will the rest of the world just render without issues or? I start to see some black squares too. It's a new world and we have had quite some trouble moving our huge spawn over, was hoping to do the render as quick as possible so players can play again.

I have 8GB memory. Currently the process is on 25% and it's running for atleast 15 hours now. Is there anyway to make the render go faster? I went with a 15k worldborder this time, as the previous world went corrupted when I extended it later on.

In-game the trees are cut in half or missing. Not as bad as the chunks I had before, but still sad to see on a new map.

I tried to run frequency 100, but within just 30 minutes I need to reatart the server or it starts giving errors about memoryGC.

The dynmap looks really bad. Running dynmap fullrender now but it doesn't seem to change anything to the black squares. Did wb fill fail even tho it said 100%?

That would only be possible if CraftBukkit ignored the World.LoadChunk method being called for some reason, which I have never known to happen before, or for that matter to be possible. Dynmap on the other hand does have a tendency to (usually temporarily) not render certain chunks.

One way you could be absolutely sure they're generated though would be to run the Fill again.

When removing Dynmap it really improves the render speed, even if your dynmap is PAUSED.