What to do after hitting the dreaded 256 max connections Apache Limit

That article is inaccurate; MaxClients can be raised above 256 when using the prefork MPM (which is what I assume you're using currently based on your description of the problem). From the documentation:

For non-threaded servers (i.e., prefork), MaxClients translates into the maximum number of child processes that will be launched to serve requests. The default value is 256; to increase it, you must also raise ServerLimit.

ServerLimit is the one that has the hard-compiled limit, but it's way past where you should ever reach without your server running into some other bottleneck. Documentation:

There is a hard limit of ServerLimit 20000 compiled into the server (for the prefork MPM 200000). This is intended to avoid nasty effects caused by typos.

So, if you want to raise your client limit to something like 512, then:

MaxClients 512
ServerLimit 512

You should also take a look at which MPM you're using, as MPMs other than prefork are better for scale. See here for more information.