While other answers provide good points, I feel that I still disagree a bit. So, I will share my own thoughts on this point.
In short, I think featuring the constant 'as is' is a wasted opportunity at best. Perhaps it is the best we are able to get for now, but it is far from ideal.
But first, I think a brief excursion is nessecary.
When do we have an effective algorithm?
When Daniel Sank asked me what I would do if there was an algorithm for factoring prime numbers with a $10^6$ factor speedup on a test set of serious instances, I first replied that I doubt this would be due to algorithmic improvements, but other factors (either the machine or the implementation). But I think I have a different response now. Let me give you a trivial algorithm that can factor very large numbers within milliseconds and is nevertheless very ineffective:
- Take a set $P$ of (pretty big) primes.
- Compute $P^2$, the set of all composites with exactly two factors from $P$. For each composite, store which pair of primes is used to construct it.
- Now, when given an instance from $P^2$, simply look at the factorization in our table and report it. Otherwise, report 'error'
I hope it is obvious that this algorithm is rubbish, as it works only correctly when our input is in $P^2$. However, can we see this when given the algorithm as a black box and "by coincide" only test with inputs from $P$? Sure, we can try to test a lot of examples, but it is very easy to make $P$ very big without the algorithm being ineffective on inputs from $P^2$ (perhaps we want to use a hash-map or something).
So, it isn't unreasonable that our rubbish algorithm might be coincidentally seem to have 'miraculous' speedups. Now, of course there are many experiment design techniques that can mitigate the risk, but perhaps more clever 'fast' algorithms that still fail in many, but not enough examples can trick us! (also note that I'm assuming no researcher is malicious, which makes matters even worse!)
So, I would now reply: "Wake me up when there is a better performance metric".
How can we do better, then?
If we can afford to test our 'black box' algorithm to on all cases, we cannot be fooled by the above. However, this is impossible for practical situations. (This can be done in theoretical models!)
What we can instead do is to create a statistical hypothesis for some parameterized running time (usually for the input size) to test this, perhaps adapt our hypothesis and test again, until we get a hypothesis we like and rejecting the null seems reasonable. (Note that there are likely other factors involved I'm ignoring. I'm practically a mathematician. Experiment design is not something within my expertise)
The advantage of statistically testing on a parameterization (e.g. is our algorithm $O(n^3)$? ) is that the model is more general and hence it is harder to be 'cheated' like in the previous section. It is not impossible, but at least the statistical claims on whether this is reasonable can be justified.
So, what to do with the constants?
I think only stating "$10^9$ speedup, wow!" is a bad way of dealing this case. But I also think completely disregarding this result is bad as well.
I think it is most useful to regard the curious constant as an anomaly, i.e. it is a claim that in itself warrants further investigation. I think that creating hypotheses based on more general models than simply 'our algorithm takes X time' is a good tool to do this. So, while I don't think we can simply take over CS conventions here, completely disregarding the 'disdain' for constants is a bad idea as well.