A good example of a WordPress based “Tutor website” is the mgrmusic.com Music Teacher Database.
Using the Geo My WordPress plugin users can search the database for music teachers local to them. The can also filter the teachers dependant on instrument or level, so this achieves two of the aims you mentioned in terms of the “search page”.
As for sign-ups; tutors submit information via a Contact Form 7 plugin form on a Sign-Up page and receive enquiries in a “Community” area of the website where enquiries are send to teachers, enabling them to respond to the students. I am not sure about how this website facilitates payment from either the teachers or students, however, I am sure you could add some type of Paypal payment facilitation that creates the release of a download file upon payment, in the file a student could find a teacher’s contact details. The whole website is ran on WordPress so it is certainly achievable to create a tutor website based only on WordPress achieving the aims that you set up above.
Hope this helps, I would research the plugins and theme options out there.
