I asked why they couldn't just use the Grant Login Access protocol and their reason is that as the app isn't installed from the appexchange, they cannot be granted access.
That's an oversimplification, but is most likely truthful. There is a special package called LMA (License Management App) that needs to be installed in a vendor's org to use this feature. Older orgs, like my really old Dev Org from 2007, would have been able to install this because they just handed out the installation link to anyone who asked.
At some point, they changed this policy and only provided this LMA installation link as part of the Partner on-boarding process, so the vendor would have been vetted first for potential security problems. I'm pretty sure if I tried to use my outdated version of LMA, it wouldn't allow me to log in as a subscriber even if they granted me access.
Can managed apps come from outside the appexchange?
A managed package is separate from AppExchange. All managed apps start out this way by default. The listing is added later. All you need is an installation link and optional password. You yourself could create a Developer Edition org if you wanted to play around with this feature and see how it works.
How do I know that this is legit? Are they gaining access to our data and selling it?
If they have an admin account, they would have access to everything, there's no immediately obvious way to know. You may want to invest in Event Monitoring if you suspect they may be stealing data, or you may be able to request audit logs for a user for some time (I don't know if they still offer this service, since EM is superior to the older log requests). You can use those logs to determine what they've done, including reports, exports, etc.
The issue is that now every issue that occurs is immediately put down to the fact that they do not have admin access.
Not having admin access shouldn't affect the app, but of course would hinder their ability to debug the application. That said, if you have any major concerns about the vendor, you should probably change vendors to someone you can trust, or perhaps even get a developer of your own, which isn't intrinsically expensive compared to having a outside vendor handle your code.
For example, vendors typically charge $200 or more per hour of work, charged in very small time slices. If they had to work on your project for even one work day a week, you could have paid your own developer for a whole week or two, and you'd have more control over your own project.
