Well if you have the resources for rest API's I guess theres no real push to go to MQTT. Although the ability to subscribe to a topic rather than repeatedly poll an API endpoint might make your system more responsive. The list of public brokers is merely for the PoC stage- you can get paid plans or run your own infrastructure if you wish.
Otherwise the hosted redis or mongodb might suit as they are only generally charged on data stored not requests made. There are obviously paid plans for those too.