One thing I wonder about, as password hashes get both processor and memory-hard -- are we presenting a trivial DoS attack on our servers, by basically letting any IP submit a request for a server to dedicate this (non-trivial) level of RAM and processor to a given task (hashing a random string to verify that this login is not correct)?

I suppose the answer is yes, but it's worth it. It's possible to fix this sort of hole (partially, at least) by capping the number of hashes processed concurrently. But most simple implementations will just assume "we're not likely to have more than X users every signing in concurrently, so we can set the work factors based on that plus some headrooom".