How should a site respond to automated login attempts with phony usernames?

But what's the point of this type of activity?

Your guess is as good as anyone's - perhaps the operator is mistakenly trying to access a set of spam accounts created elsewhere? (or ones which were supposed to be created at your site but failed for whatever reason)

Edit: ... speaking to your initial question:

How should a site respond to automated login attempts with phony usernames?

It is not a good idea to inform potential attackers whether or not the account which they are attempting to log in to exists... otherwise, no special response is necessary (unless the volume of bad requests is impacting performance).

A typical "Invalid username or password" + "Please enter your e-mail address to begin the account retrieval process" form should be served up.

Brute force works. Period. It doesn't mean they're going to compromise your site but if they try this on enough sites eventually they're going to get in somewhere. It's an unfortunate fact that many websites are poorly designed and/or built and attacks like this work. Basically it's the same principle spam. Spammers spam because it works. Even if only .01% of users respond when you send out millions of emails that suddenly becomes a lot of users and translates into a lot of money.

If there is any kind of pattern to the usernames or IPs obviously start to block those requests. Otherwise just have faith that your site is built well and isn't vulnerable to this kind of attack.

I see this type of behavior on my site as well. While it's tough to prove, I think it's just a bot crawling your site and filling in forms hoping that any submission they make could somehow be publicly viewable. The bots don't seem to be very smart in that they can't tell an account registration form from a blog comment form, so they just fill them all out.

If you see similar activity on other forms on your site, this very well could be what is happening to you. My suggestion would be to add a hidden captcha to your form. For example, add a textbox named "URL" (url fields are great spammer bait) that is hidden from human users through CSS (display:none). If this field is filled on on submit, you know that you can ignore it. There are many more methods of dealing with bots, but quite often, the simple things do the trick.