Yeah, agreed. We had used it so far simply because it was convenient. I do still think it's important for StartSSL to be very clear about this to their existing customers though - it's a breaking change of sorts.
And they are definitely not, but thanks. :) They're in an AWS VPC which is only internet addressable via explicitly defined servers. The default is to not provide a public IP.
As someone else mentioned, creating a PKI is probably the way to go at this point.
And I suppose double check that none of them are binding interfaces they're not supposed to, if any of those have interfaces with public IPs.