Does anyone know why as an Admin I can see custom records using the global search 'page:' prefix, but I can't as a non admin?

Try Perform Search permission. Take note though of its implications on other searches like saved search.