I'm taking inspiration from the title of another thread.
It's generally acknowledged that things like castles and medieval fortifications as a whole are less than useful in a world with D&D style magic in it.
As a whole, yes. In particular, Edwardian style fortifications with large open baileys and exposed fighting tops are less useful because of flight. However, even that might not be a fair appraisal because IRL the things we think of as Edwardian castles are just ruins with all the wood bits removed. There is good evidence that in a fighting posture, an Edwardian castle had covered fighting positions. Because of things like Fireball, covered fighting positions are actually more important, and not less. An army in the field is easily blasted. An army behind a prepared fighting position gains Improved Evasion.
If you move your imagination from England to the castles of Switzerland, Austia, Poland, and the Slavic Kingdoms where they tended to have small or enclosed baileys and permanent stone fighting positions - adaptations which were in part due to the less mild weather as well as greater political insecurity - then you have castles which largely work well in a fantasy setting with flight, fireball, and the like. Note also that the multiple door system acts as a pretty decent anti-invisibility defense, especially when combined with trained dogs.
All you really have to do then is invest a small portion of your castle building budget on magical defenses.
In general, the effect of magic is to increase the effective tech level by a few degrees in ways that don't exactly parallel the development of technology in the real world. For example, while I've fiat ruled that there are no stable explosives in my world to keep firearms away, one reason that something like gunpowder never really catches on is that its relatively easy to set something on fire from a distance. On the other hand, shield walls and heavy infantry are generally more important than heavy cavalry, so you never quite get away from Alexander the Great style combined arms approaches. Military science stays at a higher level than it did in feudal society. Medicine is also much more highly evolved - arguably more sophisticated in many ways than modern medicine. Light is also comparatively cheap at least in urban areas - which has a huge impact on quality of life.
Similarly, feudal style social stratification would fall by the wayside very quickly when some talented kid off the farm could develop Sorcerous abilities out of nowhere.
Not necessarily. Wizards and witches were already part of the real world medieval caste system - each in their own way. In a world with real magic, you'd just expect different new castes to open up, with whether they were an honored craftsman caste or hunted criminal caste depending on their ability to conform to the larger societies expectations. In my game, wizards are a respected caste all their own, with certain rights and dignities afforded them (as long as they play by the rules)
while sorcerers are considered to be monsters lacking even human rights. Some 1st level talented kid off the farm better hide his talent thoroughly, because a 1st level sorcerer is no match for a couple dozen veteran guards and witch hunters. Conversely, a wizard of noted ability would have the same sort of place of honor as a doctor or scholar of noted skill Regardless of his birth, he would be a celebrated figure at court and would be courted and paid highly and allowed far greater freedom to travel and to hold unusual opinions (though not unlimited freedom) than ordinary persons.
Consider a world where the "Will of god" can be known with certainty, and independently verified from anywhere on the continent.
It would be a world quite similar to one with a Holy Book, canonical interpretation, and a Pope who can speak the will of God. The main differences would be that the 'Pope' would have even more temporal authority (as a spellcasting cleric with similar servants), and that there would be dozens or even hundreds of such figures competing for authority. Collectively they would have an even greater role in ordinary life the Catholic church, though individually they would be much weaker. In general, I call this the 'Etruscan Model', and since good evidence for Etruscan ritual no longer exists (save for the testimony of the Romans), I tend to model my cultural trappings in part after India.
Consider a justice system where the innocence or guilt of an accused criminal can be verified with 100% certainty, using the right magics.
Hardly. And to the extent that this is true, it's like saying that the guilt or innocence of an accused criminal can be verified with 100% certainty by the inquisitorial authorities using the right torture. Who watches the watchers?
Consider a world where trade can occur over vast distances in the blink of an eye, thanks to spells like Itemize/Shrink Item and Teleport.
This is a big one, though in practice how much of an impact this really has depends on whether there are a lot of 9th level casters. In my game world, Amalteen had one arcane caster capable of casting teleport for a nation of 200,000 people. Talernga, the big regional power with a half million inhabitants had three, but one is now dead and the other two are not loyal to the Thrones and are serving their own interests (though one has actually been doing stuff like this secretly to increase the profits of his front organization a merchant/trading company).
In its broad effect, the increase in long distance travel and communication explains the relatively small number of extant languages, the uniformity of measurements and currencies, the relative uniformity of the availability of food stuffs, and the general lack of cultural isolation compared to the real world.
Consider a world where pretty much every national border can be bypassed by anyone who can afford the Wizard's services, where an enemy can use things like Teleport Circle to drop troops directly into your capital city, or even your bedroom.
Sure, but the number of casters in the whole world that can cast Teleport Circle is tiny. There is one in Talernga currently, and he's the first one in this region in 80 years and the nearest competitor is 600 miles away. But to the extent that these are around, they've also fortified their residences against this sort of thing. To the extent that these are around, they generally are uninterested in helping kings do their thing, and they generally don't like doing anything that other archmages might consider overly aggressive. It's true that if a city has an archmage, other rulers do not plan to besiege that city or do anything to tick that person off, but its equally true that the ruler of that city doesn't consider the archmage to be a mere subject that you order around. "Don't meddle in the affairs of wizards.", has a lot to recommend it. Conversely, wizards find that, "Don't meddle in politics.", is good advice.
What does this world look like?
Depending on your demographic and cultural assumptions, whatever the heck you like.
