Since you don't describe your relationships, my guesswork may not perfectly match what you actually have in place.
You can use a calculation field as a match field that returns a value when no company is selected that matchs to all contacts.
Say your current relationship is:
Bills::CompanyID = Contacts::CompanyID
Change it to:
Bills::cCompanyMatch = Contacts::cCompanyMatch
define Bills::cCompanyMatch as:
If ( IsEmpty ( CompanyID ) ; -1 ; CompanyID )
and clear the "do not evaluate if all referenced fields are empty" check box.
Define Contacts::cCompanyMatch as:
List ( CompanyID ; -1 )