The fallback is "multi-domain certificate", which means, if you host 10K domains, your server will send a certificate which contains 10K certificates within (a very large chunk), before anything can start. This solution is not scaleable obviously.
It'll scale OK to 10s or perhaps 100s of addresses though. OK so out-of-date people still using IE on XP will experience a slow start when accessing those sites, but if they are running "classic IE" slow obviously isn't a problem for them!
It isn't just IE-in-XP though: there are a surprising number of people still using Android 2.x on the last generation or two of smartphones and IIRC SNI was only added to the stock Android browser in v4, so if your site is otherwise mobile friendly this is going to be a concern. If the overhead per certificate is a few Kb and that multi-domain cert needs to be as large as them all then 100s of names will mean several hundred Kb in the inital handshake which may be both slow and costly depending on the user's mobile network.
Though as has already been pointed out for a larger number: if you need to be using 100s of names and can't get hole of at least a few more IPv4 addresses to spread them around there is something either technically or financially wrong with your plans!
This is of course on of the reasons why we need IPv6, as this would become a complete non-issue. Unfortunately IPv6 support is going to be lacking a lot longer than SNI support is as ISPs would much rather mess with hacks like NAT and SNI instead of investing in upgrading the base network.
