Behat started failing again with some unexpected warning:
PHP Warning: DOMXPath::query(): Invalid expression in MOODLE_25_STABLE/vendor/symfony/dom-crawler/Symfony/Component/DomCrawler/Crawler.php on line 832
Cause of problem was simple, a new release by symfony ;) (Just kidding, they are doing awesome job)