Spent about 4 hours looking for horses on a multiplayer server but was unable to find any. Tried checking old and new chunks. I went through at least 10 different plains without seeing one horse.

I am able to find them on singleplayer worlds almost immediately.