Skip to the bottom portion (my real guess).
When you start in safe mode, I don't think any macros will run.
Are you sure you were in safe mode?
If you're positive it's not in the code in that workbook (make sure you look
under ThisWorkbook and the worksheet with the problem), then it might be a
workbook that does some special stuff (application events that can look across
any workbook).
Chip Pearson has some notes on application events at:
http://www.cpearson.com/excel/AppEvent.htm
And some notes about "normal" events at:
http://www.cpearson.com/excel/events.htm
But even better he has some notes on how to find startup errors (and it sounds
like you need to isolate what loads when you startup excel) at:
http://www.cpearson.com/excel/StartupErrors.htm
Essentially, you're going to move stuff out of your XLStart folder and uncheck
everything under Tools|Addins. (But keep track!)
Then one by one, you'll add one back and restart excel to see if that caused the
problem.
===============
I just reread your post about pasting causing the trouble (sometimes).
My revised guess is that you're copying non-contiguous rows (like 2,6,18) from a
filtered range to a brand new worksheet.
Excel will convert those formulas to values.
If the rows are all contiguous, then you'll get the formulas.
I'm putting my money on this one! Don't tell me I'm wrong.