The Traktor Kontrol S4 Mk2 is a quality 4 deck all-in-one style controller that is well supported in Mixxx. Now that the Mk3 is available, you can find used Mk2s for relatively cheap. Searching eBay from the USA right now I see one for $250, another for $350, and another for $500 including a flight case/stand.
The Pioneer DDJ-SX2 is another quality 4 deck controller that works with Mixxx. Likewise with the Kontrol S4, now that the DDJ-SX3 is available I see some used ones for sale relatively cheap (~$500-$600). It is significantly bigger than the Kontrol S4, which you may or may not like.