I had the same problems. I then decided to change the NoData cells to a value (http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/How_to_change_NoData_cells_to_a_value/009z000000ms000000/). After that the tool "Extract Multi Values to Points" worked absolutely fine. It is probably time consuming, if you have to change NoData to value for each Raster. Instead I used a simple loop (python-script) to do it. That was fine for me then. I hope that helps you somehow!
... View more