Large nonlinear acoustic waves are discussed in a four-component plasma, made up of two superhot isothermal species, and two species with lower thermal velocities, being, respectively, adiabatic and cold. First a model is considered in which the isothermal species are electrons and ions, while the cooler species are positive and/or negative dust. Using a Sagdeev pseudopotential formalism, large dust-acoustic structures have been studied in a systematic way, to delimit the compositional parameter space in which they can be found, without restrictions on the charges and masses of the dust species and their charge signs. Solitary waves can only occur for nonlinear structure velocities smaller than the adiabatic dust thermal velocity, leading to a novel dust-acoustic-like mode based on the interplay between the two dust species. If the cold and adiabatic dust are oppositely charged, only solitary waves exist, having the polarity of the cold dust, their parameter range being limited by infinite compression of the cold dust. However, when the charges of the cold and adiabatic species have the same sign, solitary structures are limited for increasing Mach numbers successively by infinite cold dust compression, by encountering the adiabatic dust sonic point, and by the occurrence of double layers. The latter have, for smaller Mach numbers, the same polarity as the charged dust, but switch at the high Mach number end to the opposite polarity. Typical Sagdeev pseudopotentials and solitary wave profiles have been presented. Finally, the analysis has nowhere used the assumption that the dust would be much more massive than the ions and hence, one or both dust species can easily be replaced by positive and/or negative ions and the conclusions will apply to that plasma model equally well. This would cover a number of different scenarios, such as, for example, very hot electrons and ions, together with a mix of adiabatic ions and dust (of either polarity) or a very hot electron-positron mix, together with a two-ion mix or together with adiabatic ions and cold dust (both of either charge sign), to name but some of the possible plasma compositions.