Question: I was wondering why executables (written in c++) have to be recompiled from sources on every linux machine, even if the machines are software and hardware the same?

I had a search engine, written in c++, and I have to recompile it every time I want to move it on a new linux machine to make it work.

Any ideas?

Answer: 
It normally shouldn't be necessary to recompile. Many applications are distributed as executables and they work fine.

What errors do you get when you just copy the executable and run it on a different machine?

Maybe the problem is with the way you're copying the executable, it might be corrupting it.
The recompilation is ensuring you get optimal performance on your machine, because each time the configuration script is running to find dependencies and settings. This also ensures the openness of software as its source is always available and is modifiable by an appropriate agents - that is us.