Completely agree, a game that requires both parties to agree before they can be added to each other's Friends list should remove that connection as soon as both parties don't agree.
This is a different situation. Perhaps in your particular case, you moved servers to get away from certain people, but it's far from the only reason people switch servers. Some people move in spite of still having good friends on their old server, because they think another will be more crowded, or less crowded, or they also have other friends on the new one. And a very common reason (I'd suspect the most common reason) for people to later move back to their original server is when they miss the old friends they had there. If SE can maintain Friends lists through server transfers, that's a good thing overall.
