java.util.Date クラスが immutable じゃないのは、Calendar の登場した 1.1 以降では設計ミスだね。Hashtable と Map インターフェースのように、以前との互換性を保ちつつより抽象化されたインターフェースを乗っけてほしかった。
意図しない変更を避けるために日時データは基本的に long 型で持ちまわるようにしているが、DateFormat で文字列化する時に毎回 Date インスタンスを作成するオーバーヘッドが気にかかる。気にかかると言っても気持ち悪い程度の問題ではあるが。