While the Achievement / Trophy describes completing millennium tower without the boot up key, in order to get to the tower you need to obtain it (by defeating Eddy). This is confusing. When starting the Millennium tower stage it will prompt you a question asking if you would like to use Nancy (the giant robot in the arcade mode), which is "the boot up key" in the description. select circle (no), and finish the level to unlock the Trophy / Achievement.