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".
Yes. In fact I once was really surprised to find out how big of a fee electrum can calculate only because you have alot of inputs in the sending address.
The more transactions you received in the bitcoin address you sent from the higher your fee would be. It's best to let your wallet calculate it for you.