There seems to be some confusion here with regards to downloading and verification. I think Mike's system above shows the issue clearly: When downloading via nios2-download (and therefore "Run" and "Debug" in the IDE), everything in your .elf file is (attempted) to be downloaded to the board. If you have code linked into non-volatile memory (Flash, ROM, etc.), this will be included in the .elf.
However, the download process does not and cannot program flash (such as EPCS chips) or initialize rom -- there are separate facilities for that (Flash Programmer, Quartus' ability to initialize on-chip ROM, etc) -- all downloading can do is write to RAM. Once the download has completed verification should (correct me if I'm mistaken wombat!) simply read-back the contents of memory at all locations specified in the .elf -- this includes non-volatile memories (flash/rom, etc.).
On one hand, I can see the confusion this may create. Verification is a great feature to have to verify that RAMs are written successfully, but since the download process cannot program flash (such as EPCS in Mike's example), that can create some confusion. However, from the perspective of ensuring that your application (contained in your .elf file) runs successfully, verifying that all memory contents are initialized to expected values is also important.
I should note that the above is heresay based on my understanding of how these tools work (that is, I have not yet reconstructed this exact experiment on a board in front of me). A great way to verify this (no pun intended) would be to take your compiled application, program any flash memories, re-compile in quartus (if you have on-chip ROMs that need their initialization .hex files refreshed), and then try the download/verify operation again. By contrast, if there is an easy way to not link data into your .elf that is destined for the EPCS controller, that may also be feasible.