An advanced search for contacts with a relationship to contact '%' returns a list with all contacts with at least one relationship of the specified type. However actions on the results list also include contacts with no relationships specified.
To recreate this on the demo:
1. Ensure there is at least one Organization entry in the database with an 'Employee of' relationship to an Individual, and at least one Organization with no 'Employee of' relationships.
2. Perform an advanced search selecting: Contact Type - 'Organization' AND Relationship of type 'Employer of' that matches '%'. Results will include all Organizations with at least one 'Employee of' relationship.
3. Click the 'all X records' radio button and perform an action such as 'Add Contacts to a Group'. Now, the number of records is X + Y, where Y is the number of Organizations that didn't have any 'Employee of' relationships.
I'm not sure what the desired results of matching a wildcard character in relationship matches is (i.e. do you want to included records that don't have any relationships? my thought would be no.) but the selected records should be consistent between the results page and the actions.