A directory (like any file) is not defined by its name. Think of the name as the directory's address. When you move the directory, it's still the same directory, just like if you move to a different house, you're still the same person. If you remove a directory and create a new one by the same name, it's a new directory, just like someone who moves into the house where you used to live isn't you.
Each process has a working directory. The
cd command in the shell changes the shell's current working directory. The
pwd command prints the¹ path to the current working directory.
When you removed the directory A, what this did was to remove the entry for A in its parent directory. The directory A itself remained in the filesystem, but in a detached state, with no name. It was not deleted yet because it was in use by a process, namely the first shell. When you changed the directory in the first shell, the directory was finally deleted. The same thing happens when a file is deleted while a process still has it open: the file's directory entry is removed immediately, and the file itself is removed when it stops being in use.
Similarly, observe what happens when you move directories around.
mkdir one two
touch one/1 two/2
In another shell:
mv one tmp
mv two one
mv tmp two
In the first shell:
1 is in the directory that was originally called
one and is now called
two. The file
2 is in the directory that was originally called
two and is now called
¹ More precisely, a path, which may not be unique if symbolic links or other subtleties are involved.