Did you actually try putting it in the OUTPUT chain? I have rules for that on my router and it is definitely working (just checked with tcpdump).
I just tried this now.
Chain OUTPUT (policy ACCEPT 4504 packets, 857K bytes) pkts bytes target prot opt in out source destination 170 27734 MARK tcp -- any any anywhere anywhere tcp dpt:openvpn MARK set 0x4aa
So this time the packets are actually getting marked, but they still go out over the wrong interface. It looks like because the routing decision has already been made, it doesn't bother to look up the routing tables.
What kernel? It is definitely working for me. Are you using tcpdump to determine that the packets are going out over the wrong interface? James