I think I could have bought the small number of Jedi a little easier if there were 'lay Jedi', and the 10,000 Jedi which report to the Jedi Temple were more like upper level clergy.
I can buy the idea that the Catholic church is a large and influential organization with worldwide reach and branches in almost every country even though there are only about 5,000 Catholic bishops in the world. I can buy that because 'bishop' is an administrative title--they have lots of people working under them, both clergy and parishioners. The Jedi don't really have this, so it's hard to buy the idea that they have enough manpower and reach to do their duty.
I can also buy that the Catholic church is big and influential enough to be considered a sovereign body internationally, even though there are only about 5,000 bishops. There were special considerations made which resulted in this real-life arrangement, just like there were arrangements made in-universe regarding the Jedi's relationship with the Republic. (If there were only 5,000 CATHOLICS, I can't see such an arrangement being made.)
I can't buy the idea that a group whose population is maybe 15,000 tops (I have no idea if the 10k number means just Masters/Knights, if it includes Padawans, if it includes babies, if it includes people who never got up to the next rung of the career ladder, w/e so we'll say it's plus or minus a couple thousand people) can police an entire galaxy, when the NYPD alone has 35,000 officers to patrol a city of about 9 million. The FBI has a comparable number of employees, with over 13,000 special agents--and they're understaffed for the work they're expected to do. And we're supposed to believe that a group of just 10,000 Jedi can effectively patrol a galaxy with trillions of citizens, even with the support and sanction of the government? Unless the Republic sends a large detachment of workers of various sorts to serve the needs of a given Jedi (or unless the Jedi can supply their own warm bodies to do the work necessary in any given location), it's hard to imagine Jedi being able to get anything done on a galactic scale.
As an aside, any time I see the Jedi being referred to as genetic supermen, I hear this in my head, and I can't stop laughing.