The distinction goes as far back as we have data. Already in Middle Japanese (MJ, Heian period) the verbs were divided into two classes, one with the stem melody LL…LH-, the other HH…HL-;¹ that is, they had a mostly flat pitch, and flipped the tone at the very last mora.² These two patterns correspond, to a great extent, to classes A and B in modern dialects (with a few verbs switching classes here and there). We don’t have tone data for Japanese before this period, so there’s no clear picture of how it evolved. But the reason why all verbs fall into two accent classes is surely that the accents (at the end of the day, a restricted tone system), in all their numerous dialectal variants, have developed from these 2 older tone patterns.
In the case of nouns, the MJ tone system was richer; it had more distinctions than than modern Japanese dialects. But for verbs (and i-adjectives) it only had 2 classes, like its modern reflexes. AFAIK there’s no definitive answer as to why. Martin speculates that maybe verbs were all created with some sort of formant morphemes, now lost, and those levelled the melodies into the 2 simpler patterns. However that may be, I don’t think there’s any obvious explanation anymore as to why a given verb is A or B.
Notice however that having only 2 word melodies is a common pattern, cross-linguistically; Norwegian and Swedish do it, and in Japan Kagoshima and some Ryūkyūan languages evolved in that direction for all words, nouns included. Moreover, having different tonal rules for uninflected and inflected words, as MJ did, is not unheard of, either; Navajo does much the same.
By the way, I’d suggest not worrying too much about deliberately memorizing the accent locations.
Notes:
1) In the Kindaichi reconstruction class A (e.g. modern umaru) in MJ starts high and flips to low before a suffix: úmárì-té, HHL-H. In the Ramsey reconstruction it was the opposite, ùmàrí-tè, LLH-L. And class B (e.g. urámu) was exactly the other way around: ùràmí-té LLH-H for Kindaichi, HHL-L úrámì-tè for Ramsey.
2) In class B verbs with ≥4 moræ, the switch happened one mora earlier: modern ayamátsu < MJ àyàmátì-té LLHL-L (Kindaichi) / áyámàtí-tè HHLH-L (Ramsey). Compare modern anticipations of class B vowel-stem verbs: okíru / ókite, awaséru / awásete.
Under the Ramsey reconstruction, the first HL drop in the MJ melody became the Tokyo accent (this works for the various noun classes, too). So class B ends up with the accent on the penultimate because the basic MJ pattern, HH…HL-, gives you an HL drop at the penultimate. And class A ended up unaccented because there was no HL drop within the stem, LLL…LH-. (Notice however that MJ class A dropped the pitch after the stem, so we could expect class A in Tokyo to end up final-accented; and, interestingly, we actually do have a drop following A verbs (unlike unaccented nouns), though it shifts to the suffix if there's one: hajimeru˺ga, hajime˺wa, hajimeta˺ga; ireru˺ga, ire˺wa, ireta˺ga, etc.)
