The Plugin based Auto Numbering solution suggested by KHeiman here is brilliant.
It can be packaged in Microsoft Dynamics CRM 2011 solution, can be deployed online and take advantage of the plugin built-in transaction support feature.
One thing to note though, is that plugin transaction spans across all execution pipeline events. That means that the transaction will begin on the first pre-event plugin registered for the message/entity combination and will end after the last post-event plugin registered for the message/entity combination is executed. If you rely on plugins to perform time consuming operations, the transaction lock may last longer that you expect, locking the auto-numbering functionality and slowing down record creation process.
One way to work around this, is to place the auto-numbering plugin last in the plugins execution order, if the required business functionality allows this. This will shorten the transaction lock to minimum and improve the record creation process efficiency.