I paid the highest fee I've ever paid to get a transaction through. This was almost 12 hours ago. It's sitting there pending, along with the minimum fee and recommended fee transactions I've done since two days ago.
Did you maybe include spare coins that were left in an adress you sent before? I have read that this will be a problem because the spare coins are not confirmed because the first transaction is not confirmed. So another transaction basing on that will only get confirmations when the first transaction gets one.
We'd have to see the transaction in order to say anything about that, maybe it's an unconfirmed input, maybe the transaction size is just quite high, there are alot of options which could prevent a transaction from being included in a block despite paying a "highest fee [you've] ever paid".