OK, so after hours of testing I've finally fixed my Map. It was definitely a caching issue, despite me previously trying every combination of IsTileCachingEnabled and RequestCacheLevel options on both BingMaps and OSM providers.
Things that didn't work:
Changing IsTileCachingEnabled to false.
Any of the settings for RequestCacheLevel.
Manually deleting the cache (as suggested by Martin above).
Checking for proxied network connections.
What did work:
I set the provider to OSM and ran my app. Whilst it was running, in Visual Studio I used the Live Property Explorer to find the Provider property of the map. The OSM provider has a property called 'Layer' (BingMaps does not have this, although I guess it's 'Mode' property fulfils a similar function). When I changed this property from 'Standard' to 'Cycle' - after a short pause - suddenly the map loaded all tiles properly (albeit the 'Cycle' tiles). I then changed back to 'Standard' and all the tiles loaded correctly for that layer too.
I closed the app and changed the provider back to BingMaps, and when I ran the app again, it too loaded all tiles correctly.
IsTileCachingEnabled was true and RequestCacheLevel was CacheIfAvailable for both maps during this test.
I suspect that changing the Layer on the OSM map at run-time forced the cache to invalidate, although I can't say why this didn't happen when changing the RequestCacheLevel at design-time or run-time. Perhaps that is something that Telerik should investigate? It seems odd to me that the options to alter caching behaviour seemed to have no effect at all during hours of testing...