時間がかかるかどうかの問題かと。

といっても、未更新のとき限定だし
短縮できるかどうかは、Last-Modifiedではなく304を返すかどうかの話だけど。
(ブラウザは、Last-Modifiedがない場合、Dateを元にIf-Modified-Sinceを渡すはず)