To run Firstbits, you need a complete copy of the block chain. Most nodes will not have a full copy in the future, so you'd have to rely on a central service.
The miners as always would require the entire block chain to discover the public key corresponding to the 'first bits' but the sender does not. The sender only signs a transaction to an address, he does not verify that the receiving address is valid nor that anyone has the corresponding private key.
Firstbits seems broken right now:
Firstbits.com happens to also be a web service by the same name. But the concept is decentralized. It is a deterministic FACT derived from the chronological appearance of addresses in the block chain.
