What's the best way to use binned data in a tree-based model?
For a complete decision tree, either of your proposed models would be able to represent the same set of concepts since a decision tree can be decomposed into a disjunction of conjunctions. I don't think the fact that the bins have different sizes is really an issue because placing any significance on the exact location of splits occurring "inside" a bin is probably not a good idea anyway. From a performance perspective, what probably matters most is how your data are distributed (i.e., does your concept split the data between a single pair of adjacent bins or is it more complicated).

Since you have the "random-forest" tag associated with your question, I'm inclined to agree with you that keeping them ordered is probably better because if you are generating many trees, the ordered representation will likely result in more terse/smaller trees.