Depending on how desperate you are, and how much time you can spend on programming instead of simply purchasing more hardware (or time), there are a few other possibilities:
Use Coro. It implements cooperative multitasking in a much more programmer friendly way than POE. In fact, you will likely not need to rewrite your existing codebase, as it hooks into the IO stuff of Perl as well. It has the slight drawback that DBI queries still block your whole application (and every "thread" in it). There is a (POE) module to hand out long running queries to a separate process, and likely you will be able to abuse that module under Coro too. Coro is very picky about your version of glibc - you need to have version 6 (or higher).
Use Apache. Yes. Use Apache. Apache has a very extensive multithreading/multitasking framework and can be used to serve data/process/pass data, not only on Port 80. For example, mock wrote a mailserver using the Apache API (I think Apache::SMTP). If you have the time and manpower, using the Apache framework can give you lots of C-powered leverage while you still use Perl.
Updated: Added "on programming" in the first sentence to clarify where the time is to be allocated, at programming time or runtime
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>