※何度かやっているうちにプロジェクトを作り直したら、この現象は発生しなくなった。
おそらく2018.3.7f1から2019.2.7f2に移行した時に発生したと思われる。
下記以外にも色々な挙動不審な問題が発生したので、
Addressable Assetsのバージョンを変更した場合は注意したほうがよさそう。
他に遭遇した人の為にメモしておく。

挙動をチェックしていたところ、どうも謎な挙動をしていたのでメモ。
というのも Addressables.LoadAssetAsync() とかでAssetBundleを開いていると、Caching.ClearCahce()が実際失敗しているのにTrueを返すっぽいのだ 　

検証スクリプト

// TestSprite.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.AddressableAssets;
using UnityEngine.UI;

public class TestSprite : MonoBehaviour
{
    [SerializeField]
    private AssetReference SpriteAsset = default;

    // Start is called before the first frame update
    void Start()
    {
        Addressables.LoadAssetAsync<Sprite>(SpriteAsset).Completed +=
            op => GetComponent<Image>().sprite = op.Result;
    }
}

SpriteAssetにはRemoteLoadPathに設定しているグループの適当な画像を設定している。
接続先はLocalHostingからダウンロードしてくる

// TestManager.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
using UniRx;
using UniRx.Triggers;

public class TestManager : MonoBehaviour
{
    [SerializeField]
    Button btnClear = default;

    void Start()
    {
        btnClear.OnClickAsObservable().Subscribe(x =>
        {
            var res = Caching.ClearCache();
            if (res)
            {
                Debug.Log( "Clear cache!" );
            }
            else
            { // 失敗しているのに、こっちが呼ばれない
                Debug.Log( "Cache clear failed." );
            }
        });
    }
}

ボタンが押されるとキャッシュを削除するだけのスクリプト。

当初、Addressable Assetのキャッシュ機構の挙動について調べていて、
AddressableAssetSettingsの"Use Asset Bundle Cahce"が有効の場合は
AssetBundleと一緒らしい（つまり内部的には UnityWebRequest.GetAssetBundle を使っているハズ）みたいなので
正常にキャッシュがクリアできるかどうか上記のスクリプトを試していた。
が、思うように削除されずアセットサーバーを落としてもAsset Bundleが読み込まれる始末。

結論から言うと、Asset Bundleを使用しているシーンでキャッシュ削除しようとしていた為に
単純にAsset Bundleを開いている場合はキャッシュを削除出来なかっただけなのだが、
Caching.ClearCache()がずっとtrueを返していた為、これを検知することが出来なかった。

Unity Forumsにも多分同じ事を投稿している人がいた。
Cache wont clear at first app start

シーンを分けAddressables.LoadAssetAsyncする前にClearCacheを実行すると正常にキャッシュをクリアすることが出来た。
（サーバーを落とした状態で読み込みに失敗する） しかしこれはバグなのか、キャッシュクリアは違う方法を使わないといけないのか謎である。