Actually it is possible to add provinces to the map mid game. It just results in those provinces having no history, or owner, or controller, or anything. But you can then add that stuff manually later on. It's tricky but it can be done. I once decided to split a province in three mid game and so made some adjustments. Adding the two new provinces wasn't impossible, although it was kinda tedious.
The tricky thing would probably actually be making changes to the Trade Map. Your map would probably use most of the old map for the provinces that already existed because if I remember correctly the save actually does record what Node each province is a part of in the province's history likely as a relic from when Paradox first made the system and hoped to make it dynamic and interesting. New provinces would be unassigned until you manually added their history entries. Routes would also be wonky and the Western Europe Node's deletion could probably cause a crash. Again though, I've added Routes mid game, so it should be possible, it will just require a lot of manual editing of the save.