If your first character targets an enemy that gets defeated before your second character has a chance to go, both in Final Fantasy I and II for the NES, that character will simply attack nothing and waste their turn. How hard would it be to correct this so that it functions like Final Fantasy III and beyond?

Final Fantasy III did not entirely fix this problem. If you single-targetted magic on a target, and it dies before you cast it, it won't seek a new target (and hence, you hit nothing).

As per the question, I don't think FF1 uses anything to signify presence except for HP. Don't quote me on that though, since I haven't actually seen the code to know for sure. Just a wild guess. In any event, if there is a bit that determines it, you'd need to determine which type of battle you are in first. (9 for small, 2 large and 6 small, 4 large, and the fiends/chaos) Then you'd run it through all possible positions in that formation, and check for monsters that have the bit still set (alive) or have HP greater than 0. The final step would be to pick between the remaining monsters at random.