I was the former GM of Yahoo BOSS (was there from pre-launch through 11/09). BOSS does still exist - http://developer.yahoo.com/search/boss/. It is now a paid API under the umbrella of Yahoo Developer Network. The pricing plan (http://developer.yahoo.com/search/boss/#pricing) is based on query type and volume. Unfortunately there is no self-serve advertising model (meaning if you incorporate Y!/Bing search ads, the service is free). It's important to note though that this is the Bing search index, not the old Yahoo Search index that is effectively shut down. The original BOSS product was based on Yahoo! Search.
From what I have heard BOSS continues to do very well and is pointed at internally as how to turn an API into a real business and product.
One more note, I am now at Factual where we are very happy consumers of the CommonCrawl service.