I do think it would go slightly against the vine they want to achieve, that is to have link aggregators more than search engines. Though I don't think it would be impossible to build a search engine. It would be complicated, constricted and would need to do some tricks here and there, but I think it would be possible.

I have also thought that it would be great if there were a firefox extension that let you browse gemini. I don't know if it would be possible, but it would probably had a nicer interface than lagrange.