>And finally, the last purchase I made with bitcoins on steam took more than 12 hours to get validated. I used the standard bitcoin fee of the bitcoin-qt client but it seems to be far from enough nowadays.

So you know what the problem is, but you pretend that it's not your problem. If you use any modern bitcoin wallet, android or not, it'll automatically append a reasonable fee, and validate in about 2 seconds.