The only problem I see is that firstbits lookup requires full blockchain scan, which is sort of expensive.
"sort of expensive" ? Really expensive and getting more expensive all the time. And absolutely impossible for a lightweight hardware or mobile-phone wallet, which I think a lot of people will use as their second-factor device.