So did you lie about your address on the credit card application? If not, that’s how the bank knows you don’t live in the US and that’s why you were rejected.
Lemme simply: Either you need credit history in the US or you need to live in the US. You fail both criteria. Maybe your rejection letter only mentions the first reason, but banks definitely issue cards (with very low limits like $2k) to students with zero history. Speaking from experience.
> same primary bank for 20 years
Then walk in there and apply for a card after you get back in the US.