Hm. It never occurred to me that provable randomness might be useful... As stated, I don't think your scheme works because of Sybil attacks:

1. I come up with some easy NP problem or one already solved offline
2. I pass it around my 10,000 fake IRC nodes who all sign it,
3. and present the solved solution to the network
4. $$$