The BitlashRedisClient example that ships with Bitlash might be a useful source of ideas, even if you don't use the code, which is here: bitlash/BitlashRedisClient.pde at master · billroy/bitlash · GitHub (and more about Bitlash here: http://bitlash.net)
Here's how it works. Redis is an in-memory database server with publish/subscribe capabilities. You set up a Redis instance somewhere (on your web server, or maybe a free one from http://RedisToGo.com). Your Arduino connects to the database and listens for commands (by subscribing to a command channel). Then your PHP web application connects to the database and sends commands to the command channel as needed. Any arduinos connected to the channel receive the commands to be executed. (There are libraries that make this easy on the PHP side.)
The key feature that allows this to work around firewall issues is the persistent outbound TCP connection from the Arduino to the database. Unlike an HTTP connection which comes and goes for each request, the TCP connection can hang around as long as you like, so the arduino is in effect always listening for another command.
In the BitlashRedisClient example, the data that moves over the wire is Bitlash commands, but of course it can be anything.
Hope this is helpful; good luck with your project.
-br