Using a database, xml file, or some other datastore, record the date and time of every call to the service, and if it did any work. Every time the service is called:
1) Check the count of the records in your datastore that did work within the last 60 minutes.
2) If less than X, do work, record that you did work, and when.
3) If more than x move the request to the queue, record the request.
You'll need something checking your queue of work to be done too (windows service?), and to determine if the work done in the queue counts against your X times per hour or not.
This is all very high level as we know nothing specific about your project, HTH.