Solved by fetching the tags manually first
tags = Tag.where("name LIKE ?", "%#{@query}%").pluck(:name)
@companies = Company.tagged_with(tags, :any => true)
However, this required my to create an empty Tag
model, which isn't created by acts_as_taggable.
Maybe not the best solution, but it works :)
I'll rather do this "hack", then to write my own tagging models.