Video Cache, HD Cache...
This is an academic point, but I'll post it for posterity:
There are three caches involved in SL textures - the RAM on your Video Card, System RAM, and the Cache on your Hard Drive.
The Hard-Drive cache may or may not store an object / texture after it is deleted - I'm not familiar with its inner workings... But it IS size-limited (see your Preferences settings); so anything in the cache may be "bumped out" if the thing is filled up with a "newer" texture (i.e. something used on a prim after the object you rezzed & deleted the first time).
The Video Cache is only used by the video card to draw the current screen contents. Anytime there's more texture information than can be handled by the card's RAM, this information is transmitted and stored temporarily off the card (i.e. "paged"

out to System RAM or other appropriate "holding area" (again, it can depend on the system, the app, and the drivers for the vid-card). So its a complex interplay.
If the textures are rezzing "fuzzy" and being refined, I would assume that its being re-downloaded for some reason. The only reason to have low-detail textures (other than legacy video-card support) - is so that the data can be streamed over the 'net quickly, and then "refined" in later communications-passes. This behavior you're seeing may be a deliberate effect based on the way SL is programmed (the client may have been programmed to assume that objects / textures may be modified between instances of rezz'ing - so it can't "trust" its cached texture). If the textures were stored on your HD cache, there would be no reason for them to be "blurry" when rezzed at first.
There are such things as "Mip-maps" and "mip-mapping chains", which can be used for low-detail textures on objects a long distance away... But this is purely a mechanism to save Video-card RAM on objects too distant to make out clearly; and wouldn't apply in this case. Furthermore, mip-map levels can be switched nearly instantaneously - so you shouldn't see a "delay" as the texture is being refined. One frame the texture would be blurry, the next - *bang* - it would be clear as a bell.
Hope this information is useful - or at least satisfying to the curious.

Take care,
--Noel "HB" Wade
(Tread Whiplash)
P.S. Also for the curious, it occurs to me that you could still have the "no trust" client (which is useful in MANY ways), but still allow for caching of textures between "rezzing" instances of an object. You could add a "last modified" time-stamp to every object, texture, sound-file, and resource that the client caches; and upon rezzing, the server transmits the timestamp of the various components. If they match the cached resources, then the client does not need to re-download anything. However, this does of course increase the amount of data the servers must store in the databases - and increase the amount of information transmitted over the 'net, anytime a resource is being sent to the client that is NOT in the client's cache. Not sure whether or not it would be a help - and for all I know, something like this might already exist in the code-base; but doesn't apply to the situation posted here, for some odd reason.