Percona XtraDb cluster auto increment
We've made some tests. It turns out that auto-increment thing works completely different, so my concerns were meaningless.

With three nodes each insert into the table updates auto-increment index of a table completely. So you're always have not used values, only in rear cases where two inserts from different nodes are coming simultaneously then ids can appear one after another.

This brings us to another thought. If we have five nodes we're gonna be out of INT(11) five times sooner than with an ordinary non-cluster table.