@rjk stupid question, why would the freshness of the coins make any different in a mixer? Are you solely going off the part that older coins can be mixed more cause of the low tx fees?
The idea is that those using the service will want newer and less-"tainted" coins in return, and the way they can get those is by convincing miners to get their dirty coins by paying them a percentage. I think many miners would happily receive "dirty" coins in exchange for their fresh ones, as long as they are being paid up to 1%.
In practice it would be a bit difficult because few pools pay with brand new coins. However, many of those pools will be paying fairly new coins with little history. With the upcoming coin control patches being implemented, you could also have a feature where you could enter an arbitrary bitcoin address and be told the fee up front before transferring coins. That way, you would be able to see whether you are going to be paid, or whether the mixing will cost you.
For example, Eligius and P2Pool coins would be paid the full 1% because they are brand new. All other pools' coins might be paid 0.8%, since it can be proven that they were part of a pool payout, but just aren't "brand new". On the flip side, coins that have been used a lot could be charged between 0.8% (minimum fee for non-pool and non-coinbase coins) and 2% for coins that have been used a lot. 2% to 3% would be for coins that others might consider stolen or tainted for some other reason, and the mixer would make its money off of the spread.
Perhaps even the user submitting extremely "dirty" coins could select the freshness of the coins that they want back, in exchange for a lower fee. For example, someone that has a few coins that would normally cost 3% could choose to pay the full fee and get some Eligius coins back, or pay a partial fee in exchange for some other very used coins that came from a different user.
I don't know whether there is a demand for any such service, but I would assume that the 1% payout would create a disproportionately large demand on the miner side. This would obviously be a problem if only those eligible for a payout are using the system, instead of both types of users.
Anyways, that's my idea and I can't create it, so it's out there in case someone else wants to make it. It would require extremely careful design in order to actually work as expected and not fail due to lack of use by both sides of users. Perhaps if a paying user does not show up, the users that expect to be paid will be told to wait, or will have their coins mixed with other new users at no fee instead of negative fee if they select that as an option.
