14 июня 2000 года президент Владимир Путин, находившийся в Испании, на просьбу прокомментировать арест главы "Медиа-Моста" Владимира Гусинского заявил, что хотел бы получить больше информации от генпрокурора, но тот "недоступен для связи". Владимир Устинов в это время представлял в Екатеринбурге своего заместителя по УрФО.
9 июля и 17 сентября 2000 года в программе НТВ "Итоги" ведущий Евгений Киселев высказал сомнение в законности получения генпрокурором квартиры на Тверской улице. По словам господина Киселева, господин Устинов не заплатил налог с квартиры, приобретенной при посредничестве бывшего управделами президента Павла Бородина. В октябре 2000 года генпрокурор подал на журналиста и телекомпанию иск о защите чести и достоинства, 30 января 2001 года Мосгорсуд его удовлетворил. 19 февраля ГКУ признало законность получения квартиры.
23 августа 2000 года Владимир Устинов возглавил группу по расследованию гибели подлодки "Курск". 27 октября 2001 года по телевидению был показан семиминутный фильм с комментариями генпрокурора, снятый на поднятой лодке в доке Росляково. 1 декабря 2001 года генпрокурор доложил Владимиру Путину о промежуточных итогах расследования, после чего в отставку были отправлены командующий Северным флотом адмирал Вячеслав Попов, начштаба флота вице-адмирал Михаил Моцак и еще 12 офицеров. Выяснив, что причиной катастрофы стал дефект одной из торпед, Генпрокуратура закрыла дело.
В мае 2001 года разгорелся заочный спор между Владимиром Устиновым и замглавы администрации президента Дмитрием Козаком. Последний предлагал создать единый вневедомственный следственный комитет — федеральную службу расследования, которому предлагалось отдать все дела, расследуемые милицией, налоговой полицией и прокуратурой. Устинов выступил с резкой критикой этого предложения, и оно в итоге было отвергнуто.
15 ноября 2001 года генпрокурор лично возглавил группу гособвинителей в процессе над чеченским боевиком Салманом Радуевым. 25 декабря 2001 года Верховный суд Дагестана приговорил террориста к пожизненному заключению, спустя год он скончался в тюрьме от кровоизлияния.
5 сентября 2002 года Владимир Устинов презентовал свою книгу "Обвиняется терроризм", в которой исследовал феномен терроризма на примере Северного Кавказа.
В октябре 2004 года вышла вторая книга прокурора "Правда о 'Курске'". Размышляя о трагедии, автор, в частности, пришел к выводу, что "сейчас в России наступает важнейший этап тотальной борьбы с ложным разумом, зависящим от толстосумов и, зачастую, коррумпированных и не очень далеких людей".