You may want to checkout
www.ringcentral.com. In addition to offering toll free numbers they also offer a virtual pbx service. Initially we registered our toll free number with Ring Central and later ported it over to Fonality
www.fonality.com since we recently setup a HPBX for our office.
I believe Fonality also offers TF numbers but in terms of price ringcentral is pretty affordable and reasonably priced within the market. Even if the 1-800 number you want is not available it would be a wise choice to have a toll free number with coverage for US/Canada Vs. assuming your clients have a nationwide long distance plan.
Unfortunately, the number we wanted within the 1-800 exchange was not available so we had to register a 1-888 since we feel that is is more memorable vs. 1-877 or 1-866 and they now have 1-855.
Cheers,