One of the things that will make it tough for future IMS deployments is the need to hand-over a connection to a circuit switched 2G carrier when running out of coverage of a network technology such as UMTS or LTE that can support the required packet switched quality of service and speeds. Yes, there is SR-VCC (Single Radio Voice Call Continuity) and soon even Reverse SR-VCC (see here) but it's still a long way from theory to practice.
Recently, it appeared to me that a network operator that doesn't have that sort of problem is NTT DoCoMo. They are fully relying on their 3G network for everything including voice calls (which is still handled by the MSC) so there is no need to fall back to 2G. In other words, they are in an ideal position to introduce IMS, perhaps with LTE once they feel coverage is sufficient and then seamlessly hand-over the packet switched IMS voice call to a packet switched UMTS bearer.
So as you can't get it any easier, I wonder if they will be one of the first to deploy IMS?