Just starting with J2EE myself, but will take a shot none the less,
since it looks like an interesting question.
I think you can look into JNDI Directory services,
which allows you to store attributes on objects, and supposed
to be persistent across all of the clusters.
So, I would try to create a separate JNDI name/object pair
for each possible order type, and store the last used id number
as an attribute on this object. This way you should be able to
have those order numbers unique.
BTW, that's just an idea, haven't tried it myself.