Definitely not unheard of; in fact I've heard figures as high as 6 months' rent, basically splitting the first year's revenues with the landlord.
These apartment location agencies don't work for free. Typically, they make a deal with the landlord before you ever enter the picture, in return for the agency recommending the apartment to you. The agent's name goes on the lease paperwork, and they get paid. Often, the agent will take pains to personally be present for the lease signing so he can ensure the referral information is correct; otherwise he just gave his services away for free.
If the agent has not made an agreement with the landlord, they'll typically come to you for payment. Again, the agreement for such a payment is stipulated up front before they start showing you properties and consummated when you sign the lease (possibly with a "kill fee" of time and materials even if you don't sign with any property they show you), but now it's you on the hook. Typically, this arrangement is reserved for high-value properties like downtown condos, where the landlord doesn't need a recruiter bringing clients to his door; the name of the property itself is its own marketing, and they have a waiting list. However, you, as a wealthy but busy potential tenant, need assistance traversing the complex negotiation and contracting process, which the agent is only too happy to help you with, for a price.