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.

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.