私が書いたコードとAppleのサンプルAddMusicコード（http://developer.apple.com/iphone/library/samplecode/AddMusic/index.html はデバイスのみで実行されます）の両方で問題が明らかです。
アイテムをクリックしたときにMPMediaPickerControllerを開くと、その後そのアイテムの選択を解除することは不可能のように見えます。実際には、MPMediaItemCollectionに再び追加されるだけです（これで問題ありません。後で重複をフィルタリングできます）。
何かを選択した後、選択を解除できないのは奇妙なことです。以前は、「追加」ボタンがオンとオフのチェックボックスとして機能するように実装されていると思っていました。
MPMediaPickerControllerで選択を解除する方法を説明するドキュメントに何かが欠けていますか？