tf.contrib.legacy_seq2seq.embedding_rnn_seq2seq output projection
Alright! So, I have found the answer to the question. 
The main source of confusion was in the dimensions 
[output_size x num_decoder_symbols] of the W matrix itself. 
The output_size here doesn't refer to the output_size that you want, but is the output_size (same as the size of the hidden vector) of the LSTM cell. Thus the matrix multiplication u x W will result in a vector of size num_decoder_symbols that can be considered as the logits for the output symbols.
The official documentation for tf.contrib.legacy_seq2seq.embedding_rnn_seq2seq has the following explanation for the output_projection argument:

output_projection: None or a pair (W, B) of output projection weights and biases; W has shape [output_size x num_decoder_symbols] and B has shape [num_decoder_symbols]; if provided and feed_previous=True, each fed previous output will first be multiplied by W and added B.
I don't understand why the B argument should have the size of [num_decoder_symbols]? Since the output is first multiplied by W and then the biases are added, Shouldn't it be [output_size]?