you are confusing cross realm zoning and realm connections. cross realm zoning is when an older zone has different realms all funneled into it.
connected realms are those realms where you can actually friend people because, while they still have a realm name connected to it, they are now basically one realm. they share an AH, you can join the guilds, etc.
as an example to try to explain it better:
I am on Magtheridon, which is connected to Altarofstorms, Anetheron, and Ysondre. I have toons across all four realms, and all of them are in the same guild, which is on the magtherion realm.
now, I regularly see people from Stormrage, Alexstraza, sargeras, etc as I play. this is because of cross realm zoning, which was implemented to make zones seem more populated as you level. it also occurs when you join a group where the leader is on another realm. this is the reason you see people from realms that aren’t connected to yours in major cities. you will not be able to trade gold, join guilds, or friend people from these realms.
so the people you are trying to friend are not on a realm connected to yours, they are just zoned into the same instance of the zone you are in.
I hope this helped you. I tend to get longwinded and confusing when trying to explain things.
Edit to add: it just occured to me, you may be trying to friend someone on the same realmset as you, but are forgetting to add the realm name onto it. for example, if someone on Ysondre tried to friend my DK after working with me, but just typed “Silvine” then they’d get the “character not found” message because, while Silvine-Ysondre does exist, she is not logged in. because thats my DH. typing just the name, and not including the realm suffix automaticaaly looks for the character with the name you typed on the server you are on. a person on Ysondre wanting to friend my DK would have to type Silvine-Magtheridon.
they kept the server names so that people would not have to rename all their toons when the servers were connected. because some have had the same name since vanilla (not me. I started in wrath.) it can make it a bit confusing at times, especially when one in your guild basically copies everything about your toon and joins the guild to confuse the heck out of you and the guild when you ding every ten levels… (not me… okay, yeah i did that, lol. try it sometime. it gets amusing.)