I just saw my department administrator dealing with a whole bunch of envelopes on her desk.
I think the reason why rejection letters are sent out late is that they have to send A LOT (hundreds!) of them!!
Formal/Quant oriented programs like NYU and Rochester don't care about foreigners' GRE verbal.
But you definitely need a good TOEFL score and 800 or close on GRE math, I believe.
GRE Quant is becoming increasingly important in admission decision in PoliSci PhD program. I would say you need at least 700 to get in NYU ( or Rochester or Stanford) since the mean score for those admitted is like 750 there..