UPDATE:
The #REF! errors were not returned randomly in a broad sense, they appear sometimes and once the first occurrence appear on one cell then it repeats to the cells below it.

This looks to be a latency problem inherent to GOOGLEFINANCE(), as was previously mentioned by [Normal](http://webapps.stackexchange.com/users/79865/normal) in a comment to the question.

In order to have a "rock-solid formula" instead of using GOOGLEFINANCE directly in column E use an auxiliary sheet to hold the historical currency conversion rates as fixed values instead of calculated values through a formula.

You could use GOOGLEFINANCE() to get that data but then copy and paste values only.
 
<hr>
#Short answer before the OP shared a demo spreadsheet

Instead of using ambiguous date format (00/00/0000) use a explicit one like

- dd/mmm/yyyy
- mmm/dd/yyyy

among others
 
#Explanation
The problem could be due to the regional settings / date format of your spreadsheet / data.

I just tried to reproduce the problem but it works fine in my environment:

- Date format: dd/mm/yyyy
- Regional settings: Mexico
- Account language: Spanish Latin America
- Always show the function names in English

[![using dd/mm/yyyy as date format works fine][1]][1]


  [1]: https://i.sstatic.net/ATXEB.png

#Reference

- [GOOGLEFINANCE - Google Docs editors Help](https://support.google.com/docs/answer/3093281?hl=en)