Well, the benefit to YC is that they can get a better feel for companies which may fully apply to a class for a somewhat nominal fee. Stronger branding, bigger presence, and just doing some cool shit to boot.
I agree that people need to be aware that their company should offer some benefit to YC as well, just simple business...exchange of value.
But what can you offer them?
It's clear what YC Fellowships offer to companies, but I suspect there's also some not-as-obvious benefits to YC.
Would Tarsnap bring these benefits to YC?