There is little use in having two columns to encode a single binary variable. The reason for this is that one of the columns (equal to 0,1) is sufficient to describe the binary content. The second column simply is a linear combination of the other, when the first is equal to 1 the second must be equal to 0 and vice versa in a binary setting. So the information in the second column is redundant. It may even be harmful to have such two (perfectly correlated) columns.
Case with one variable (0,1) to distinguish the groups:
Binary encoding as "dummy variable" generally works as "contrast". You are right that there is some kind of "order" in this type of encoding. However, the order only matters in terms of a contrast ("1" versus "not 1"). Consider a simple linear regression with two "dummy encoded" groups. Recall that a linear regression with only the intercept term (or additional dummies) simply gives the mean of $y$.
df = data.frame(y=c(9,10,11,19,20,21),x=c(0,0,0,1,1,1))
summary(lm(y~x,data=df))
It is easy to see that for group $x=0$, the mean of $y=(9,10,11)$ will be $10$ and for group $x=1$ the mean is $20$. A linear regression $y=\beta_0 + \beta_1 x$ will yield:
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 10.0000 0.5774 17.32 6.52e-05 ***
x 10.0000 0.8165 12.25 0.000255 ***
So the mean of group $x=0$ is $10$ (the intercept) and the mean of group $x=1$ is $20$ (intercept + coefficient for $x * 1$ [the dummy]).
Group 0: $y = 10 + 10 * 0 = 10$
Group 1: $y = 10 + 10 * 1 = 20$
Now when you revers the encoding (change the 0,1 indicator for the groups):
df = data.frame(y=c(9,10,11,19,20,21),x=c(1,1,1,0,0,0))
summary(lm(y~x,data=df))
The result will be:
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) 20.0000 0.5774 34.64 4.14e-06 ***
x -10.0000 0.8165 -12.25 0.000255 ***
Group 0: $y = 20 - 10 * 0 = 20$
Group 1: $y = 20 - 10 * 1 = 10$
So just "reversed". Now the group with mean 20 is the reference, and the mean of the other group is defined against this reference as $y = 20 - 10 * 1$.
So the "order" (the way you encode 0,1) makes a difference here which can be descibed as "10 more than the other group" in one case and "10 less than the other group" in the other case.
However, in predictive models this "order" plays no or little role. It only matters if you want to directly interprete the estimated coefficients.
Case with two variables (0,1) - one for each group:
df = data.frame(y=c(9,10,11,19,20,21),g0=c(1,1,1,0,0,0), g1=c(0,0,0,1,1,1))
summary(lm(y~g0+g1,data=df))
The result will be:
Coefficients: (1 not defined because of singularities)
Estimate Std. Error t value Pr(>|t|)
(Intercept) 20.0000 0.5774 34.64 4.14e-06 ***
g0 -10.0000 0.8165 -12.25 0.000255 ***
g1 NA NA NA NA
So one of the "indicators" is dropped because of perfect collinearity of $g1$, $g2$. The information contained in $g2$ is redundant and cannot be digested by linear regression. So here it is "harmful" to have $g1$ and $g2$ in the model at the same time.
It may work to have $g1$ and $g2$ (both at the same time) in models such as random forest because of the way these models are calculated (perfect collinearity is not necessarily a problem there). However, the information will usually not bring "new insights" (since the information of $g2$ is already present in $g1$ and vice versa). It may however cause "confusion".