If you have good_records >> bad_records then you can use:

select distinct country from location_address
minus
select distinct country from location_address where
upper(substr(country,1,1)) < 'A'
and
upper(substr(country,1,1)) > 'Z'
and
upper(substr(country,2,1)) < 'A'
and
upper(substr(country,2,1)) > 'Z'

in this case you should create and analize 3 indexes:

1) create index aaa on location_address(country) ....:
2) create index bbb on location_address(upper(substr(country,1,1))) ....:
3) create index ccc on location_address(upper(substr(country,2,1))) ....:

execution plan probably will be:

1 - FULL fast scan on index aaa
2,3 - RANGE scan on indexes bbb, ccc

Try.