Николай I подписал решение генерал-аудитора. Однако на стороне Яцына выступил прекрасно знающий всю подноготную этого дела бывший начальник штаба Черноморского флота контр-адмирал Мелихов, ставший в это время товарищем (заместителем) генерал-аудитора. Яцын подал прошение о пересмотре его дела, причем снова обвиняя Грейга и его жену в хищении больших сумм денег и лоббировании приближенных купцов при получении подрядов на строительство флота. Грейг, живший уже к этому времени в столице, не на шутку испугался возможных последствий, ведь могло начаться новое расследование! Встревоженный Грейг торопится уверить Николая в своей преданности: «Сия мысль (о воровстве. –
Причем Грейг не только клянется в своей любви к императору и своем «отвращении зла», но далее требует ужесточения наказания для Яцына, а заодно и расправы над еще одним своим недругом – контр-адмиралом Мелиховым. Николай I, которому уже поднадоели слезницы Грейга, распорядился никакого нового дела не начинать, а старое за давностью времени прекратить. Тогда же Мелихов добился и возвращения Яцына полковником на военную службу, причем с зачислением ему всех проведенных за решеткой лет в служебный стаж, т. е. фактической реабилитации и компенсации за нанесенные обиды. Пусть с большим опозданием, но правда в данном случае все же восторжествовала.
Грейга заносило все больше и больше. Так, он пытался командовать инженер-капитаном Бурачковым, подчиненным лично князю Меншикову. А когда тот установил факт очередного воровства, Грейг пытался его арестовать, но адъютант Меншикова успел покинуть Николаев раньше, чем за ним пришли. За Бурачкова Грейг получил нагоняй от царя.
Еще большим получился скандал с главным кораблестроителем Черноморского флота полковником Александром Кирилловичем Каверзневым, одним из талантливейших кораблестроителей своей эпохи. Поначалу отношения Грейга и Каверзнева складывались неплохо, но едва кораблестроитель уличил обер-интенданта Критского в воровстве ценнейшего подольского корабельного леса и попытке заменить его дешевым и некачественным маломерным, Грейг сразу же взял сторону своего любимца. Каверзнева же огульно обвинили в «нецелевом» использовании леса и арестовали, сделав на него начет на 118 тысяч рублей, которые тот не мог бы выплатить и за пять жизней. Каверзнев потребовал объективного разбирательства. Инспекторский департамент Морского министерства очень быстро установил, что дело против Каверзнева сфальсифицировано. Испугавшись последствий, Грейг пошел на попятную, но Каверзнев заявил, что более служить с ворами не желает, и подал в отставку. Так как терять специалиста такого уровня Россия себе позволить не могла, Каверзнева высочайшим указом перевели подальше от Грейга, на Балтику, где его талант раскрылся в полной мере.
Еще более резонансным был конфликт Грейга с начальником штаба Черноморского флота В.И. Мелиховым. Василий Иванович Мелихов был не среднестатистическим офицером, а настоящим интеллигентом и интеллектуалом. Он много плавал, а помимо этого был сведущ в делах административных. В 1922 году Мелихов был уже начальником распорядительной части в канцелярии Черноморского департамента. Должность немалая, но и ответственная. Именно Мелихов предложил Грейгу создать Морскую библиотеку в Севастополе для занятия досуга офицеров. В 1826 году Мелихов предложил Грейгу создать первый на Черном море штаб флота.
Во время Русско-турецкой войны 1828–1829 годов Мелихов как начальник штаба и «правая рука» Грейга участвовал в осаде и Анапы и Варны, возглавил отряд «охотников», который ночью на шлюпках отправился к крепости и неожиданно атаковал и захватил стоявшие под берегом турецкие суда. За захват этих 14 судов Мелихов получил от императора чин капитана 1-го ранга.
После окончания войны отношения между Грейгом и Мелиховым испортились. Официально – из-за разногласия в распределении «призовых денег». На самом же деле – после появления в Николаеве Леи Сталинской, которая всеми силами старалась ему пакостить.