If the PoW cost is a low-end cellphone CPU for 2.5 minutes, then it's nothing to the spammer with the 200-core hourly AWS server. If each spammer can create 10000 identities (not connections, identities) per hour, then you might as well not have a limit at all. If they could even create only 2 identities per day that would be enough to spam with (yet still unacceptable to actual users). 250000 identities per day is way too many.
The speed ratio is much smaller than you say with memory-hard PoW problems, which depend on the amount of RAM you have (and its response time). But it's surely true that a spammer could create many accounts per day, perhaps 1000 per hour on a big server, which could then go on to spam a few accounts each before becoming uneconomical to keep using.
But that would still put the CPM of the spam around US$2, which very few spammers can afford. Maybe mesothelioma lawyers and spearphishers.
You don't have to make spamming physically impossible, just unprofitable.
A single identity can send messages to hundreds or thousands of users.
You're talking about a different proposal than the one I wrote in the comment you were replying to, then.