Yes, iCloud Photo Library is enabled on all my devices (one Mac, one iPad, one iPhone). I follow the steps you outlined. A search for a name that I know I already tagged returns the appropriate photos on my Mac and my iPad, but doesn't return anything on my iPhone. My photo library is fully synchronized on all my devices so I'm not sure why this is happening.