Polynomial-time distinguishability threshold of planted clique
My understanding is that no algorithm is known for finding cliques with polynomially high success probability for $k=O(n^{1/2-\epsilon})$.  I think it is believed that getting a polynomially large success probability is not possible.

The reason for my holding this belief is that after a clique-finding algorithm outputs a clique, one can check if it succeeded.  So if the algorithm fails, it can be re-run until the clique is found, which would yield polynomial time algorithm for polynomially high edges.  Of course, this isn't quite right -- an algorithm may be deterministic and its success could depend on the random target graph, and so this trick wouldn't work.  So this is more intuition than proof.

The paper of mine you cite gives concrete lower bounds, but only for a restricted class of algorithms.