Before addressing the central aspect of the question, I think it is important to clear up some misconceptions in the way this question is framed. When we think of medieval maps, we normally think either of a T-O diagram or one of a handful of late 13th or early 14th century mappaemundi. (Such as the Hereford map, Ebstorf map, or the Psalter World Map.) While may features of these maps are more broadly applicable, these were also all produced within about 100 years and all in a particularly devotional context, so we should be careful about extrapolating outwards from them.

Most of the features we consider characteristic in these maps were developments of the twelfth century. Prior to this, we rarely see many of these features. In terms of shape, world maps pre-1100 came in a variety of shapes.

The oldest extant mappaemundi, the Albi world map (ca. 750), is shaped like a horseshoe (see p. 116 here). The Cottonian/Anglo-Saxon map (mid 11th century) is square, as are most of the early Beatus maps (from the 10th century forwards).

Almost no maps have Jerusalem as the centre prior to the mid-twelfth century. Besides those already mentioned, none of which have Jerusalem at the middle, even some of the more classical looking maps of the twelfth century don't have Jerusalem at the centre. For example, the Sawley world map, from the end of the century, has the Cyclades and Delos in the middle. Likewise, the Munich Isidore map, from the mid-century, has Tyre at the centre. On both of these you can see Jerusalem just up and to the right of the centre.

Finally, although the relationship of circular mappaemundi to T-O diagrams is attested on the Ebstorf map (as a T diagram has been drawn in the upper right margin), we shouldn't necessarily equate the two. Indeed, the Ebstorf map is a bit unusual in its presentation of the Mediterranean in a clear T-like form (see also the Psalter Map). Most present it as essentially a big L (cf. Hereford + Sawley) or a jagged blob (cf. Higden + Vat. 6018 (f. 63v-64r) (note that this late 8th century map is also oriented south)).

But as to the central aspect of the question. We do see some local maps being produced from the later twelfth century, although mostly of Jerusalem. But we must be careful about what we mean by spatial accuracy. For the central middle ages, maps were normally viewed as equivalent with written descriptions. So the accuracy of a map was more or less what you would expect form the accuracy of a verbal description of the same area. The relative position of things is normally roughly accurate but there isn't a concern for the mathematical projection of space. Rather, the essential feature of these maps is the relative position of places.

Take for example one of the early maps of Jerusalem, from a French picture bible of ca. 1190-1200. If we compare this with a modern representation of Crusader Jerusalem, we can see that there is a definite representation of the space in the medieval image. It has the characteristic parallel streets and if you turn the medieval map a quarter turn clockwise (so that the left-right streets from st stephens gate to mt sion mirrors the north south arrangement on the modern map) you can see that it reasonably breaks down the major elements of the city into quarters very nicely. You can see the holy sepulchre above David's gate/tower (ie. the citadel), then this is beside the Solomon's Temple and the Lord's temple (together the temple mount) and above that the Church of Mary Magdalene (tempum sanctae mariae). The important thing here is not that the map provides something like a detailed street plan, but that it shows the essential features of the city, much like a modern tourist map. Compare this with the early 15th century painting of Rome by Taddeo di Bartolo. It is just a set of walls, to represent a city, filled with all the monuments of Rome in a weird empty void space. This is like how when you think of Rome now, you don't imagine a street plan, but might instead think of a nebulous city space that contains the Vatican, the Colosseum, the Pantheon, etc.

There is a greater development in the production of regional maps, which do show some concern for the accurate representation of space. From the late 12th and 13th centuries we see regional maps of Britain being produced and from the late 13th regional maps of Italy or regions of Italy. There is the related development of exceptionally accurate charts of the Mediterranean, called Portulan charts (here is one of the earliest from ca.1290-1300), although it is still very much unclear how these could have been produced. The earliest regional maps seem to be English. One of the earliest examples is in a manuscript of Gerald of Wales Topography of Ireland (note that there is an image on the page and a link to the digitalised MSS. It presents Britain and Ireland as essentially potatoes with a few of their major cities and rivers.

But, from the thirteenth century we find two examples of surprisingly accurate maps of Britain. Going in reverse order, in the early or mid 14th century somewhere in England the Gough map was produced. It presents a fairly recognisable image of Britain, albeit one that looks very much like a phallus... This is another map that falls into the surprisingly accurate category, as the relative spatial position of various cities is exceptionally accurate. While some have suggested it was made to a scale, this seems very unlikely and a more plausible suggestion is that someone has used travel itineraries and just carefully plugged the distances between cities in. This relationship between local maps and travel itineraries is likewise important for the other major map of England from the thirteenth century. In his universal history, the Polychronicon, Matthew Paris includes both a number of maps and some visual travel itineraries (which are nicely collated here). He also has a map of Britain, some of which are quite detailed, others of which are less so. Nevertheless, the latter is interesting as, in the middle (around London) Matthew has written: "The whole island should have been longer if only the page had permitted" (Si pagina pateretur hec totalis insula longior esse deberet). So again, there is a notion of scale and space emerging, but not one that we should think of as systematic or mathematical.

From the 15th century, particularly associated with the reintroduction of Ptolemy's Geography around 1406, we see the beginning of more radical changes in the form that cartography took. It is in this period, with Ptolemy and a the turn to mathematisation both from 14th century scholasticism and particularly in 15th century renaissance platonism, that we see people beginning to think seriously about the mathematically projection of space. It is here that we really start to see the production of regional maps that look like what we would expect a map to look like. For example, one of the earliest maps of Germany in produced by Nicolas of Cusa in the mid-15th century, which looks pretty much like what we would expect a map to look like. There is likewise a rich history of producing local maps in Italy, but as I know very little about them, I will point you to the article in the University of Chicago's History of Cartography on local maps in the middle ages by PDA Harvey, which is focussed predominantly on Italian and English maps from 1350-1500. More generally, the best introduction to mappaemundi is Woodward's chapter (18) in the same volume.

Edit: With relation to the perception of cities, see also this excellent post by /u/sunagainstgold. Thanks to /u/wagrid for finding this for me.