yeah, logically this is the case but the problem is, I can't trace anything out because there is no pattern to the connectivity. And the sadest part is that even I don't have any idea, how this problem can be regenerated.

please use comments instead of answer field if need info from the question owner, the answer field is only for clear answer for the original questions. Thanks!

Yes, I do have a floating-IP range on the external network. I allocated 20 floating-IPs. Yes, each instance is having its own floating-IP. One more thing I want to add that, the internal network (vm to vm connectivity) is working fine in each case.