I do most of the trading on CEX. Withdrawal fee of $3.8 (or 3.5 for eur) seems genuine considering the amounts I withdraw and more over other exchanges charge 3-5%. Of course, if you are withdrawing $20 it seems much but it is better than other exchanges.  As for legitimacy, I've been using cex for a long time, and have particularly withdrawn money to cards about 20 times, everything was ok