Generally with other ulta-orthodox baalei t'shuva or other people with similar backgrounds. That is a good idea, regardless, as the compatibility is more likely to be there. (The only exception to your list is persons of color - my observation is that they tend to find a person of a different color who doesn't have a hangup about it).
In addition, There are other members of the community that aren't on the "inside track" of shidduchim with which to make a shidduch, such as children of ba'alei Teshuva, etc. Compatibility has a lot to do with the age at which the person became a ba'al teshuva. If they started at 13/14 years old, and went through the regular school system at the end of their school years, it is very different than the 30 year old.
The main problem with this is that there is some view that those who are frum from birth from families with a long history of observance are somehow an inherently superior shidduch for a ba'al teshuva. In fact, compatibility in their life together is much more important.
In terms of where to find a Shadchan to make such a shidduch, the way to look is to find recently married people of similar circumstances and ask them how they made their shidduch, and follow those leads. You can also ask people who aren't married in a similar circumstance - perhaps they found a lead and are "in the parsha".
In the type of groups you are talking about, there are always people in the group who are very into knowing who is related to who and how they form the circle of the group (call it Olympic level Jewish geography). As such, some people always know who the Ba'al Teshuva is, so you can find out by asking around.
I am reminded of a story where a Ba'al Teshuva wrote to the Lubavitcher Rebbe that he was having a hard time finding a shidduch for his children. The Rebbe wrote him back that the other Chassidim he inherited from his father-in-law, the Ba'alei Teshuva he chose as Chassidim.
I'll tell you another story about someone I know who is in a Chabad community. He is not a Ba'al Teshuva at all (from a long line of non-Chabad Chassidim with many generations of Yichus) however he had a hard time with a Shidduch for his son because he kept the traditional clothing - streimel, etc. which was out of the norm for a Chabad family. So he looked for a Shidduch in Chassidic communities that demand large dowries from the girls (there is no such thing in Chabad circles). He found a good family that happened to be poor - and they were more than happy to make the Shidduch.
Anyway, the bottom line is that there are many such shidduchim made all the time, where people don't fit the pre-defined mold, and shadchanim who specialize in them. However, there does need to be an adjustment of expectations, which is a good thing for a happy marriage.