Well, I finally figured out the issue with the ARP not resolving. I had a manual IP address configured on an unplugged ethernet port, while my wireless was connected to the network.
The laptop would attempt to do an ARP on the ethernet port first, and ultimately fail. On the second request, it would send the ARP request out on wireless, to which it got a reply and worked. Once I disabled the ethernet adapter completely, everything worked first time though.
Been working on this all day, and to find it wasn't the Arduino after all is a good thing. I re-enabled the String functions and everything is working happily.