I don't think ultimatums are a problem at all in their current guise. Most are not microed well and get chance decloaked long before they hit anything valuable or spend so long trying to get around screens and porc that the battle moves on and whatever edge they might deliver is no longer significant.
They're a wildcard option that, if the stars align, might just turn the tide of battle. However, most of the time they are simply a micro-sink that doesn't accomplish anything worth the time put into weaving through the other side's units and structures.
If a team is reliably using fire or tremors to dispose of screens to make space for an ultimatum, all they're doing is coming up with a plan and executing it well, the essence of an RTS game. Your screen doesn't have to be fleas. If you are going to walk into the teeth of an artillery bombardment, then maybe your screen needs to be stuff that can take some pain. Losing a Minotaur or two to bust an ultimatum on a detri hunt is a small price to pay if that detri then goes on to decide the game. It's not like an ultimatum can snipe. It has to get close and it has a moderately large decloak radius.
Of course, detri probably won't go on to decide the game, but that's a problem with detri, not ultimatum. I think I've only seen one game recently where it really was the key to victory.