Comment by eqvinox

Installing a DNS server (personal preference: nsd) on a virtual or dedicated rented box seems to fulfill your mandatory conditions. Did you mean to include something like "web interface" or "managed" in the criteria? What exactly is it that you expect of the "provider" here?