Невозвращение олигархов. Прокуратура неоднократно получала отказы зарубежных стран на свои многочисленные просьбы выдать фигурантов громких дел. Бориса Березовского не выдали Великобритания (сентябрь 2003 года) и Латвия (февраль и сентябрь 2005 года). Испания (апрель 2001 года) и Греция (октябрь 2003 года) отказали в выдаче Владимира Гусинского. Фигурантов дела ЮКОСа не выдали Израиль и Британия. Отказались выдать РФ даже чеченских "эмиссаров" Ахмеда Закаева (из Великобритании) и Ильяса Ахмадова (из США).
Провал с расширением полномочий. 31 мая 2000 года Владимир Устинов предложил Госдуме дать прокуратуре право законодательной инициативы и обращения в Конституционный суд. 15 мая 2002 года он высказался за введение обязательного участия прокуроров в процедуре банкротства для выявления фиктивного банкротства. Оба предложения не были рассмотрены.
Отмена внесудебных арестов. В сентябре 2001 года Владимир Устинов убедил Владимира Путина в необходимости при принятии нового УПК отсрочить запрет на внесудебный арест до 1 января 2004 года. На это время прокуроры сохраняли право выписывать санкции на арест. 18 декабря Госдума приняла УПК с соответствующей оговоркой. Однако 14 марта 2002 года Конституционный суд сократил отсрочку до 1 июня 2002 года.
Провал в работе с присяжными. Органы прокуратуры столкнулись с невозможностью убедить присяжных в вынесении нужного вердикта по громким делам. Так, в августе 2001 года были оправданы организаторы терактов на вокзале в Пятигорске, а в октябре 2005 года — в Каспийске. Был оправдан Вячеслав Иваньков (июль 2005 года) и подростки, которых обвиняли в убийстве таджикской девочки (март 2006 года). Дважды вынесен оправдательный приговор по делу Эдуарда Ульмана (о расстреле спецназовцами мирных чеченцев).
Неубедительное расследование теракта в Беслане. В суды попали только дела единственного выжившего террориста и милиционеров из Северной Осетии и Ингушетии, хотя родные погибших неоднократно требовали привлечь к ответственности руководителей операции по освобождению заложников. Следствие по делу продолжается, но выводы фактически не меняются с сентября 2004 года. Возмущенные этим жители Беслана неоднократно устраивали акции протеста против необъективного, по их мнению, расследования теракта.
Развал дела Холодова. Московский окружной военный суд дважды (в июне 2002-го и июне 2004 года) оправдал обвиняемых в убийстве журналиста, признав, что прокуроры не предоставили достаточных доказательств. Более того, один из фигурантов дела — бывший начальник разведки ВДВ Павел Поповских отсудил у государства больше 2 млн руб. компенсации.
Развал дела Пола Хлебникова. Совершенное 9 июля 2004 года преступление Владимир Устинов взял "под личный контроль". В убийстве обвиняли выходцев из Чечни Казбека Дукузова и Мусу Вахаева, а также бывшего московского нотариуса Фаиля Садретдинова. 5 мая 2006 года они были оправданы.
Потеря связи. 14 июня 2000 года президент Владимир Путин, находившийся в Испании, на просьбу прокомментировать арест главы "Медиа-Моста" Владимира Гусинского заявил, что хотел бы получить больше информации от генпрокурора, но тот "недоступен для связи". Эти слова широко обсуждались в СМИ и стали поводом для насмешек над президентом и генпрокурором.