1965年3月、板柳から東京に集団就職する[24]。就職先は渋谷の高級果物店だった[26]。身長が160cmほどと小柄な体格で目が大きいため性別に関係なくかわいがられ、北海道育ちのため言葉の訛りが（他の東北出身者に比べて）少なく、果物店では接客を要領よくこなしていた[26]。同店の当時の常連客には女優の岩下志麻もいた[26]。やがて新規店を先輩と二人で任されるほどの信用を得る[26]。しかし、青森に次の就職勧誘に出向いた上司が板柳時代の窃盗の話を聞かされ、その後別の上司が永山にそれをほのめかす発言をしたことで、解雇されると思い込み、わずか半年で退職した[27]。この果物店に勤めていたころ、1965年7月29日には勤務先の近く（渋谷区内）で発生した少年ライフル魔事件[注 6]を目撃している[28]。果物店を退職後、荻窪にいた三番目の兄[注 7]を頼って一泊するも、それ以上いることは許されずに絶望する[31]。「南の島に行こう」と横浜港からデンマークの貨物船に乗り込んで密航したが、寄港地の香港で下ろされて日本に送還された[31]。栃木県小山市に住んでいた長兄に引き取られ、宇都宮市の自動車の板金工場で働く[32]。上京以来被害妄想にとりつかれて孤立する一方、自分を見下しながらまったく話しかけもしない長兄の態度に怨みを抱き、「当てつけ」として市内の肉屋で窃盗を働き捕まった[32]。同年11月10日には宇都宮少年鑑別所へ収容されたが、同月2日には宇都宮家庭裁判所の少年審判で不処分になった[33]。1966年早々に永山は長兄の元を飛び出し[32]、大阪までヒッチハイクで移動した[33]。

宇都宮を出て最初に勤めた大阪府守口市の米屋では、雇用主の命で戸籍謄本を取り寄せた際、本籍の欄に「北海道網走市呼人無番地」との記載があり、当時有名だった映画の『網走番外地』シリーズから、自分は「網走刑務所生まれ」だと誤解し、周囲がそれを冷やかしたり自分を辞めさせようとしていると思い込んだ[34]。雇用主の子息が東京の大学で受験の下見をすると自分の身辺調査に向かったに違いないと思い込み、店に来た公認会計士をやはり調査に来た弁護士だと考えた[34]。4月に新人が入りそうになると、一方的に退職した[34]。池袋の喫茶店、東京国際空港（羽田空港）の喫茶店と移るが、いずれも周囲の状況から自分が不利になったと速断し、逃げるように退職している（後者は同じ職場に板柳出身者がいると知っただけでやめた）[34]。手首を切って自殺を図るが果たせず、その数日後の1966年9月6日にアメリカ海軍横須賀基地に侵入して基地内で窃盗を働いたところを憲兵 (MP) に発見され、横須賀警察署（神奈川県警察）に刑事特別法違反・窃盗罪で逮捕された[注 8][36]。逮捕後には横浜少年鑑別所へ身柄を移されたが[36]、同室者からリンチを受ける[37]。

逮捕から1か月半後[38]、10月21日に横浜家庭裁判所横須賀支部で開かれた審判により試験観察処分を受けた[注 9][36]。審判の際には、関わることを拒否した長兄に代わって次兄が訪れ、母も上京して同席した[38]。次兄（当時池袋在住）の「困ったらいつでも来い」という言葉と母の上京に刺激を受けた永山は、定時制高校への進学を決意、新宿区淀橋の牛乳配達店で働きながら勉学し、1967年4月、明治大学付属中野高等学校の夜間部に入学する[41][注 10]。入学後は学業にも仕事にも熱心に取り組み、最初の中間試験は79人中13位の成績で、演劇部にも所属した[41]。しかし、睡眠時間を削っての生活による疲労に加え、保護観察官が勤務先に訪れたことで「前科者と露見する」という被害感情を募らせ、6月下旬に店を辞めてしまう[41]。高校は「保証人と連絡が付かない」という理由で8月に除籍処分となった[41]。

この後、横浜港で沖仲仕の仕事に3か月就く[42]。続いていくつかの職を転々とし、自衛隊にも応募したが基地侵入の犯歴により受験できなかった[42]。永山は再度定時制高校に通う意思を持ち、1967年10月下旬から池袋近くの牛乳配達店に勤めた[43]。だが、1968年の正月明けに電気ポットのスイッチを切り忘れて店の畳を焦がしたことで「店にいられない」と考え、「日本から逃げる」「横浜は顔を知られている」という理由で神戸港からフランス籍の船に乗って二度目の密航を企てるも失敗、船内で手首を切って自殺を図ったが、横浜に戻される[44]。横浜と東京の少年鑑別所での収容を経て、2月に再度の保護観察処分となった[45]。次兄も今度は引き取りに出向かず、代わりに訪れた三番目の兄に励ましを受け、杉並区西荻の牛乳店で働きながら、同年4月、明大付属中野高校に再入学し、クラス委員長に選ばれる[45]。ここでも学業と仕事は熱心だったものの、「辞めさせて貶めるためにわざと委員長に選んだ」という根拠のない疑いを抱き、相談しようとした三兄が不在だったことで、5月7日に配達中の牛乳を放置して売上金を持ったまま失踪し、板柳の実家に戻った[46]。