List all symbolic links to valid directories only with find

Concering your second question, if you make the symlink using a relative path and then move the whole directory structure, it still should work. Consider the following terminal session:

~$ mkdir test
~$ cd test/
~/test$ mkdir test2
~/test$ cd test2/
~/test/test2$ touch testfile; echo "hello, world" > testfile
~/test/test2$ cat testfile 
hello, world
~/test/test2$ cd ..
~/test$ ln -s ./test2/testfile testfileln
~/test$ ls -l
total 8
drwxr-xr-x 2 xxxx xxxx 4096 2010-09-09 09:18 test2
lrwxrwxrwx 1 xxxx xxxx   16 2010-09-09 09:18 testfileln -> ./test2/testfile
~/test$ cd ..
~$ mv test/ testfoo
~$ cd testfoo/
~/testfoo$ ls -l
total 8
drwxr-xr-x 2 xxxx xxxx 4096 2010-09-09 09:18 test2
lrwxrwxrwx 1 xxxx xxxx   16 2010-09-09 09:18 testfileln -> ./test2/testfile
/testfoo$ cat testfileln 
hello, world

As for your first question, if you really want a link that will refer to the same file no matter what you do with the original location of the file, a hard link is probably what you want. A hard link is basically just another name refering to the same inode. Thus, there is no difference between the hard link and the "original file." However, if you need to link across file systems, hard links often do not work and you usually cannot make hard links to directories. Further, you will notice some differences when performing some file operations. Most notably, removing the original will not remove the file. The hard link will still point to the file and be accessible.

Use the -h tar option. From the man page:

-h, --dereference
    don't archive symlinks; archive the files they point to