Well, in this case the situation was apparently one of name resolution. Apparently the server was unable to resolve "itself." Sadly, I didn't find this result when searching, but Alan Storm (the god of Magento himself) mentioned this as a problem.

So, in short, read that post for more info, but we were able to fix this issue by adding a host entry on the server. After this point, things were working once again.

<servers ip address> storedomainname.com

After chatting with @moose I've decided to post this as an answer myself. Thanks to Nexcess for pointing @moose to my write up, and thus feeding my insatiable lust for stars on my github repository.

There is a core magento configuration cache bug which causes a "No 404 CMS Page configured" error or - in other instances - a "100 router match iteration" error. The error goes away when you flush the cache, but usually re-appears after some time.

https://github.com/convenient/magento-ce-ee-config-corruption-bug

(Edit: Further changes can be added to prevent config corruption: https://github.com/convenient/magento-ce-ee-config-corruption-bug#update-2-further-improvements)

Replication

Check out my repository above.

It has a file 100-router-script.php which should help replicate the error for you by running it in the root of your website.

The Patch

Magento have released a patch (SUPEE-4755) based on my write up.

PATCH_SUPEE-4755_EE_1.13.1.0_v1.sh

This patch is the exact same as my fix which gives it some validity.

This patch isn't publicly listed anywhere because Magento don't do that for anything but security patches for some reason. I know the patch file says EE_1.13.1.0, but I tested it on community edition 1.9 and it applied fine.

You can grab a copy of the patch here: https://github.com/convenient/magento-ce-ee-config-corruption-bug/blob/master/PATCH_SUPEE-4755_EE_1.13.1.0_v1.sh

And for historical reasons or in case my github account ever gets deleted

/**
* Initialization of core configuration
*
* @return Mage_Core_Model_Config
*/
public function init($options=array())
{
    $this->setCacheChecksum(null);
    $this->_cacheLoadedSections = array();
    $this->setOptions($options);
    $this->loadBase();

    $cacheLoad = $this->loadModulesCache();
    if ($cacheLoad) {
        return $this;
    }
    //100 Router Fix Start
    $this->_useCache = false;
    //100 Router Fix End
    $this->loadModules();
    $this->loadDb();
    $this->saveCache();
    return $this;
}

If this doesn't fix your Magento instance

This patch file will solve all reasonably vanilla magento instances (anything that reinitialises the configuration cache using the defined init or reinit methods).

If you have any code which calls the loadDb function - like n98-magerun - then you're likely to have a bad time and should probably consider refactoring your code to call reinit or init on Mage_Core_Model_Config.

If you still have trouble, I recommend you read my write up and

1. Implement the logic mentioned in the Debugging the Issue section.
2. Wait for some log data to appear.
3. Contact me!

A theory on why supee 6788 makes the error worse

I've just posted this in the chat room and thought I'd pop it here for posterity.

Something to remember is that magento has ALWAYS had this bug in it's background. and that supee 6788 has just made it something that is more likely to happen

I just had a look at the supee 6788 patch for EE1.14 This is my working theory.

Mage_Core_Controller_Varien_Router_Admin was patched to override the addModule function

Now, I can't quite recall the order in which things occur during the mage request initialisation But this modification now adds two calls to Mage::getConfig()->getNode() on each single request, quite early on in the flow. If there is an object cache param failure with useCache during either of these two calls, then it could potentially trigger an incomplete configuration being written to the cache (getNode can trigger a reinit, as it tries to load values from the cache, and on a failed load, it will reinit the entire config cache and re-save it via the reinit() function)

So perhaps just adding these two extra getNodes on to a very early part of the request, when the full configuration may not be loaded could have caused this error to happen Either way I wouldn't sweat a full understanding of the issue. It'd be a lot of work for not a lot of gain, and looking into Mage_Core_Model_Config::loadDb (with a focus on what effect the useCache flag may have on it) could drive a man insane.