Z wyjątkiem dopełniacza wszystkie podane formy są poprawne. W dopełniaczu mówimy Sołoduchy (podana przez Panią forma to chyba wynik nieuwagi), w wołaczu zaś obocznie Sołoducho lub Sołoducha, np. „Panie Sołoducha, niech pan tu przyjdzie”. Według PWN-owskiego słownika poprawnej polszczyzny wołacz Sołoducho jest pretensjonalny, czasem podniosły, wołacz Sołoducha zaś – bardzo potoczny (zob. hasło problemowe nazwiska).
Podanego nazwiska nie można nie odmieniać. Nieodmieniane mogłoby być nazwisko Sołoducho, gdyby towarzyszyło mu imię, tytuł zawodowy, naukowy itp.