I'm in Canada and went through a similar process.
I started with Quicken -I couldn't quite get the hang of it, it didn't fill me with joy, and a year after my purchase they started one of those sneaky "you didn't expressly opt out via a tiny icon at purchase" monthly fees on my credit card. So, then i didn't really trust them, either.
Then I tried Mint -several issues. Like you said, the whole "violates banking agreement" issue, and -related to that- it couldn't download most of my accounts, lots of glitches.
Then I tried YNAB. I've stuck with YNAB, and continue to love it. I tried it, dropped it, and a couple of years later started up again. This time I've stuck with it for about 10 months so far. I absolutely love it. I used to enter everything manually, now I use the 'Download to Quicken' option on my bank and credit card accounts.