It doesn't really make much of a difference whether you are talking about IP packets or Ethernet frames. Neither Ethernet or IP in of themselves cares much about packet order, but re-ordering can have an impact on higher level protocols.
Re-ordering of packets within a logical connection is typically undesirable but occasional reordering is tolerable. Naive implementations of higher level protocols will often end up treating out of order packets in a similar way to lost packets and unnecessarily retransmitting them and performing congestion backoff. Some implementations may try to handle them better, but there is fundamentally a trade off between how well out of order packets are handled and how well dropped packets are handled.
For this reason when it is desired to use multiple paths to a destination at the same time (either on an Ethernet level with link aggregation or on an IP level with equal cost multipath) most implementations will try to keep each logical connection on a consistent path. This is typically done by hashing a tuple of fields that will be consistent for any given logical connection and using that hash to decide which path to use for the packet. Exactly what combination of fields is used is implementation dependent, for best balancing layer 3 and 4 source and destination fields should be taken into account, but simpler implementations may only take account or layer 3 or even layer 2 source and destination.
Of course topology changes can cause occasional out of order delivery, either because the route packets take changes completely or because the set of equal cost paths changes and hence changes the hash grouping, but as long as this only happens occasionally it is usually not too much of a problem.
As long as the implementer doesn't do something monumentally stupid a VXLAN overlay network should have reordering behavior that is similar to the underlay network it runs on top of. So if the application or transport protocol would tolerate the level of reordering it sees on the underlay network it should also tolerate the level of reordering it sees on the overlay network.