Usually it tells me it's failed just before the next 'automatch cycle' is about to start (so after a couple of minutes). In the rare cases where it doesn't I'll usually cancel with 10s to go before the next matchmaker cycle for that gamemode is about to be found.
I recall a while ago there was mention about people who cause failed games to get a time-out - is that a planned feature or implemented yet? If implemented, then it'd be good if more feedback could be given to people on why the game has failed e.g. 'Another player caused the game to fail. They wont be able to join the next matchmaker attempt', and similarly 'A game couldn't be found because of a connection issue with you. You will need to wait x minutes before you can attempt a new matchmaker game'