Run-time packers are typically used by malware-writers to obfuscate their code and hinder static analysis. The packer problem has been widely studied, and several solutions have been proposed in order to generically unpacked these protected binaries. Nevertheless, these solutions commonly rely on certain assumptions that may not necessarily be met by certain types of packers. In this paper, we propose a taxonomy to measure runtime packer complexity, and evaluate it over two datasets composed of both off-the-shelf packers and custom packed binaries. Also, we propose a set of heuristics to improve the feasibility of multi-path exploration approaches for recovering the code of packers that unprotect their code on demand.