It worked for me! Thank you @advanceduzer!
None of the suggestions worked for me so I ended up changing getAjaxDeleteUrl to getDeleteUrl in app/design/frontend/rwd/default/template/checkout/cart/minicart/default.phtml. Obviously this is a workaround and not a fix and means a page reload and not an ajax update of the cart but this is far better than it not working at all and I don't have time for further debugging.
Check if yout PHP is running as fast CGI. Switch it to module and try. Worked for me.
Sometimes cgi adds some additional header to response.