Poor network performance, server not always sending icmp replies

I've been battling poor network performance with three new servers for the past month now. This performance is present even when doing a basic ping to the server. I can pretty much recreate this issue at will. If I start up a ping from my desk to one of these servers, it will time out. How long it will time out varies. Just recently I ran wireshark on my workstation as well as one of the servers. I then started up a ping to the server. It timed out 18 times and then started responding. During the timeouts, the wireshark on my PC showed 18 ICMP requests being sent out from my PC. The wireshark on the server shows that the server received these ICMP requests. However, it never sent a reply for any of these 18. Then, everything starts working properly. Every one of my requests is matched with a reply.

What complicates this issue is that when my workstation is timing out to one of these servers, other workstations are having no problems communicating with it. It seems like leaving a continuous ping up maintains connectivity.

I realize I have spared you the details of the network environment, but I feel like since I can see my requests successfully making it to the server I can ignore everything in the middle for now.

I'm at a loss. Thoughts? I can provide the wiresharks if necessary, but they are pretty straight forward.

thanks in advance