It will all depend in your actual implementation.
If you go with regular QinQ you can define up to 4094 vlans that you can define per device (assuming a decent box).
Now, that does not means you will be able to use all of them. Neither that you will be able to transport all of them.
Remember that there are some vlans that are reserved like the range 1002-1005 and others you will probably like to avoid like vlans 1,1006-1024.
In term of transport, the extended range 1025-4094 can only be transported by VTPv3 which is not yet available for every platform. In fact, if you buy any 7600 rigth now, it will probably come with an IOS that does not support it. You will have to upgrade to a recent "ED" from January or February of this year.
Now, assuming you manage to control all that, you might end up investing in a huge infrastructure only to support 4094. The spanning tree will have to be taken into consideration because of convergence and root selection.
If you go with a pure Layer2 infrastructure, you will probably will want to consider designing some sort of hierarchy such that you can have customers Vlans inside service vlans or something like that. There are some interface cards to help with this (like the SIP400 and ES20)
There are great technologies out there and a combination of a few of them might give you a more scalable solution.
Unless you have a very specific need and don't expect to grow beyond the VTPv2 limits, and plan to maintain a small Layer2 diameter, I wouldn't recommend a pure Layer2 deployment.
HTH
-W
