How to create a special autoincrement field?
The obvious option would be to have a serial field for each type. Whether or not that is feasible based on your business rules (are there lots of types, are the types likely to change, etc.) is another question.

Another module that may be very useful in these types of problems is the computed field module.

Another option (probably the one I would choose) is to make it completely custom.
Either a custom entity property or a custom field of some sort that does database queries to determine the next value instead of auto_nodetitle + serial module + rules.
Be careful of race conditions when doing something like this though.