Phone specs and Java implementations vary a lot, but within each manufacturers range there will be groups of phones that share the same specs and implementation.
I used to work at a company making J2ME games, what we did there was test on every handset we released the game on, but we had 2 types of test - Complete and Compatability.
We would adapt a version of the game for a specific phone, eg Sony Erricson K800i, and have it thoroughly tested according to the Complete Test spec.
Once that had passed, we then used that build on phone known to have similar specs and good previous compatability with other games (we kept a database of specs and compatability records), eg Sony Erricson W910i, and submit it for a compatability test, which was a bit less thorough and a bit quicker.
Once you've been doing it a while you get to know the capabilities of phones and which phones you could use the same build on, but there is often a bit of guesswork involved :) Sometimes you get matches you wouldn't expect, and sometimes a match you would expect to work doesn't.
Edit: I was going to post this as a comment, but I can't (because i'm an SO noob :), out of interest, what phones are your Nokia's and Samsung?
I can't remember many specific handset names, but here is a quick rundown of compatability across manufacturers:
Sony Erricsons are generally excellent - if it works on one, it will likely work on all SE handsets with the same resolution.
Nokia's are generally good within a certain smaller group eg N95 builds work well on most nokias with the same res that were released after the N95, but some handsets are a bit of a pain.
Samsungs are pretty bad - the J2ME implementation on most is flawed (Hide/Show Notify methods not being called is an example), and the memory and speed are typicly a bit crap.
Motorola phones are not great, but are generally quite compatable with oneanother. Same goes for LG, although their more recent models are much better.