The link is an improvement over nothing, at a minimum it will cut down on the number of newbies posting 'how do I search' questions, at least, if they scan the footer.
Experience shows that this is probably not the case but then at least we can point them to the link without having to explain site prefixes, which is still a net gain.
If it were in the header (which is pretty crowded) it would be more useful, but I can see that that might lead to complications, if it were a miniature form in the header it would be better still, but I can see that that would really be much harder to integrate.
Searchyc.com probably can't handle the load if they are the 'sole provider of search' for HN, so it looks like that is not an option, when the HN robots.txt file locked out google because you had to crunch the numbers for the applications it was apparently touch-and-go on searchyc.
Now I'm really curious what your secret startup is that may solve the problem, and I hope they roll out soon.
I am currently part of a start-up, Favetop.com, which offers direct site searching through just the click of a site icon. I've found it to be quite convenient for searching sites directly and much better than constantly adding site prefixes or visiting the actual websites to search. You may want to give it a try and see if it helps you out.
(See how complicated such matters actually are? Nothing that goes on the front page of the site is ever a trivial matter.)