it is important to know with what reasons the Ausländerbehörde rejected your appeal. Withour knowing that it is difficult to make any assessment of your chances because there are a lot of circumstances which the Ausländerbehörde can take into account. It
The general points can be, if you work und earn your living (and have a good perspective to work for a long time), if you have enough living space (at least 12 q,m. pro Person if you live with the family), if you have no criminal story and - naturally - if you have a passport and haven't lied about your identity. But even in case everything is positive the Ausländerbehörde hat its discretionary power. It is well-known that they mostly don't give the residence permit after 25.5 very willingly even if they ought to. The reason can be also that you had a rejection as openly unfounded (offensichtlich unbegründet), in this case you can only get a residence permit without leaving Germany and asking for a visum, if you have an absolute right to stay (Anspruch). According to your description you don't have it, you only have a deportation obstacle through the children. So, as you see, it is very important to know what arguments the Ausländerbehörde or RP Karlsruhe bring to reject your appeal.
The comment that you can get a residence permit after the §25b is right, if you fulfil the conditions. You can ask your lawyer or go to a councelling center (although your lawyer would normally propose it him/herself if he/she sees this chance).
And if you have a qualified job you can chance in the permit after §19d under special circumstances. Although I believe, your lawyer would have already explained and tried it.