At the end of the day this is easier than I expected.

Example:

[[email protected] play]# find ./ -follow -lname "*"  
./somedir4  
./somedir7  
./somedir6  
./somedir5  
[[email protected] play]# ls -la  
total 12  
drwxrwxr-x. 3 bcane bcane 4096 Aug 15 18:35 .  
drwxrwxrwt. 4 root root 4096 Aug 15 18:28 ..  
drwxr-xr-x. 2 bcane root 4096 Aug 15 18:42 somedir  
lrwxrwxrwx. 1 root root 7 Aug 15 18:35 somedir1 -> somedir  
lrwxrwxrwx. 1 root root 7 Aug 15 18:35 somedir2 -> somedir  
lrwxrwxrwx. 1 root root 7 Aug 15 18:35 somedir3 -> somedir  
lrwxrwxrwx. 1 root root 10 Aug 15 18:35 somedir4 -> somedir_no  
lrwxrwxrwx. 1 root root 10 Aug 15 18:35 somedir5 -> somedir_no  
lrwxrwxrwx. 1 root root 10 Aug 15 18:35 somedir6 -> somedir_no  
lrwxrwxrwx. 1 root root 10 Aug 15 18:35 somedir7 -> somedir_no

Once you've found the broken links you can delete them easily.

[[email protected] play]# find ./ -follow -lname "*" -delete  
[[email protected] play]# ls -la  
total 12  
drwxrwxr-x. 3 bcane bcane 4096 Aug 15 18:43 .  
drwxrwxrwt. 4 root root 4096 Aug 15 18:28 ..  
drwxr-xr-x. 2 bcane root 4096 Aug 15 18:42 somedir  
lrwxrwxrwx. 1 root root 7 Aug 15 18:35 somedir1 -> somedir  
lrwxrwxrwx. 1 root root 7 Aug 15 18:35 somedir2 -> somedir  
lrwxrwxrwx. 1 root root 7 Aug 15 18:35 somedir3 -> somedir