When I use my flash application, two thirds of my attempts to communicate with
the ColdFusion CFC return wsdl errors because flash never reaches the host. If
I press the button to communicate with the CFC again, it works just fine.

Its the first load after any short period of silence... and is really a
strange issue... Does anyone have any advice on this?

I'm on two load balanced web servers behind a hardware load balancer and a
firewall.