Could you include domain names (.com, maybe .io/.ly) and maybe Facebook url? If you had those this could be great for finding pronounceable names.
It's be great if you could set it so that it would just keep trying until it found one that was available on all services, but I can see that adding a ton of overhead, so I can see why you haven't done that yet.