Is it possible for an administrator to delete pending user relationship requests (between users)?
No, there is no special administrative pages for managing other people's relationships, but this would be a useful feature.

Have a look at user_relationships_load in user_relationships.module. You could use that to create a list of all of the pending relationships site wide by passing in user_relationships_load(array('approved' => FALSE));. You can further filter that by passing in additional information such as the relationship type. UR's views integration doesn't really take an administrators needs into account but you could build this list with views as well.

Once you have that list you can generate delete links that call user_relationships_delete_relationship. Calling that function with the proper RID (relationship ID) will delete those pending relationships for you.

If you don't want to build an admin page to come back to, there is nothing wrong with doing a little clean up directly in the database as long as you're careful and back up everything first.