Ethereum - how is the output of a contract computation verified?
Other nodes do the same computation, in a deterministic fashion, and they compare their result to the result the miner got. That's why there's no function that returns random results - different nodes would come up with different numbers, and the chain would fork. All other miners verify your block, and the penalty for building an incorrect block is losing the block you mined.

But there's a related question: can you gain an advantage by improving the speed of the VM, or skipping computations somehow?

I think you could. For example, you could offload the computations to a GPU. Even though Dagger is GPU-resistant, the VMs require a small amount of memory and could probably be run on a GPU.

The advantage would be pretty slight, though.