I started compiling this bug report while being on Docker 1.9. Then I realized 1.10 is out, so I upgraded. Then I found the problem persisted (and got even more undeterministic).

docker version

Client:
Version: 1.10.0
API version: 1.22
Go version: go1.5.3
Git commit: 590d510
Built: Thu Feb 4 18:16:19 2016
OS/Arch: linux/amd64

Server:
Version: 1.10.0
API version: 1.22
Go version: go1.5.3
Git commit: 590d510
Built: Thu Feb 4 18:16:19 2016
OS/Arch: linux/amd64

docker info

Containers: 20
Running: 10
Paused: 0
Stopped: 10
Images: 309
Server Version: 1.10.0
Storage Driver: aufs
Root Dir: /var/lib/docker/aufs
Backing Filesystem: extfs
Dirs: 538
Dirperm1 Supported: true
Execution Driver: native-0.2
Logging Driver: json-file
Plugins:
Volume: local
Network: bridge host null
Kernel Version: 3.16.0-4-amd64
Operating System: Debian GNU/Linux 8 (jessie)
OSType: linux
Architecture: x86_64
CPUs: 2
Total Memory: 2.985 GiB
Name: builder
ID: DJQ3:G446:H6DX:GRRV:YTTX:EKUF:HUB2:UFUO:MFVA:G3EB:XPOU:PIAM
WARNING: No cpu cfs quota support
WARNING: No cpu cfs period support

I noticed that network interfaces in the network stack of containers sometimes are not listed in the same order, although the containers were started by the same commands in the same order.
In case source ip is not bound explicitly by applications, the kernel binds the address of the first listed interface, not the eth0's one. This in turn affects my firewall configuration.

Expected order of interfaces:
lo
eth0: main_network (the one used with run or create)
eth1: other_network (connected by docker network command)

With Docker 1.9

WIth Docker 1.9 I used the following commands:

docker run --name=container --net=main_network ...
docker network connect other_network container

I managed to reproduce the problem by repeating the above run/connect commands in a simple for loop. The order of the network interfaces was the "expected" about 98-99 times in 100 attempts.

An example when something was messed up:
512: eth1: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default
link/ether 02:42:ac:16:00:68 brd ff:ff:ff:ff:ff:ff
inet 172.22.0.104/16 scope global eth1
valid_lft forever preferred_lft forever
inet6 fe80::42:acff:fe16:68/64 scope link
valid_lft forever preferred_lft forever
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default
link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
inet 127.0.0.1/8 scope host lo
valid_lft forever preferred_lft forever
inet6 ::1/128 scope host
valid_lft forever preferred_lft forever
510: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default
link/ether 02:42:ac:12:00:67 brd ff:ff:ff:ff:ff:ff
inet 172.18.0.103/16 scope global eth0
valid_lft forever preferred_lft forever
inet6 fe80::42:acff:fe12:67/64 scope link
valid_lft forever preferred_lft forever

With Docker 1.10

WIth Docker 1.10 I used the following commands:

docker create --name=container --net=main_network ...
docker network connect other_network container
docker start container

By running these commands in a loop, the order of the network interfaces became more diverse (than it was with 1.9).

An example when the interfaces were not in the expected order:
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default
link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
inet 127.0.0.1/8 scope host lo
valid_lft forever preferred_lft forever
inet6 ::1/128 scope host
valid_lft forever preferred_lft forever
878: eth1: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default
link/ether 02:42:ac:12:00:68 brd ff:ff:ff:ff:ff:ff
inet 172.18.0.104/16 scope global eth1
valid_lft forever preferred_lft forever
inet6 fe80::42:acff:fe12:68/64 scope link
valid_lft forever preferred_lft forever
880: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default
link/ether 02:42:ac:16:00:69 brd ff:ff:ff:ff:ff:ff
inet 172.22.0.105/16 scope global eth0
valid_lft forever preferred_lft forever
inet6 fe80::42:acff:fe16:69/64 scope link
valid_lft forever preferred_lft forever