Solr ignoring NOT but works with "-" and "!"
Issue was with my implementation. Before the query was posted to Solr, I was doing following:

$query = strtolower($query);


This made the NOT to not hence it wasn't working as expected.