Минюст — существительное мужского рода.

Формальных ограничений на склонение нет, ср. Минздрав — в Минздраве, Минюст — к Минюсту. В неофициальной речи могут склоняться и названия Минрегион, Минкрым, Минкавказ, однако в официальной речи нужно использовать не сокращенные, а полные названия этих министерств. 

От официального названия Департамент здравоохранения возможно образование сложносокращенного слова Депздрав, поэтому сочетание Депздрав Москвы орфографически корректно. Однако официальным сокращенным названием, как, например, Минюст, Минтранс, это сочетание не является. От описательного оборота департамент здравоохранения образуется нарицательное слово депздрав (ср.: колхоз, исполком). Употребление оборота депздрав Москвы в качестве неофициального обозначения организации возможно.