Would creating an nonclustered index with the same column(s) as the clustered index be the most efficient?
To properly mimic the clustered index in this way you would need to INCLUDE all the non-indexes columns as well as covering the same one(s). This will be inefficient space-wise as you are adding a full extra copy of all the table's data in that index and will affect insert/update performance (though for many use cases, which are read-heavy this is not as significant as you might think).
If you don't INCLUDE everything with your fake clustered index then you will likely harm performance of any queries that specifically reference it because you now have lookups back to the clustered index for columns not covered by the new one.
What does the optimizer do in this case - does it still make a plan to include these "bad" indexes that just reference the clustered index, or will it know to ignore the with(index) request?
I assume it will do as it is told and use the specified index, only referencing the CI if you don't INCLUDE everything needed. That should be easy to setup a sample test environment to verify.
In an effort to improve performance, I deleted some unnecessary indexes
Removing unnecessary indexes will only usually help with inert/update performance issues (and reduce burden on maintenance burden by not taking space in backups or being rebuilt/re-orged if you regularly do that with all indexes) so if read performance was your concern then just put them back in as they were.
be the most efficient?
If there are not other complicating factors, putting the original indexes back as they were would be your most efficient solution IMO, whether or not you leave your new ones in place (as they may help other accesses).
What other ideas could cause this behavior?
Would a forced plan that references a dropped index still get used and therefore cause errors when the plan is enacted? This is a feature I've not used so just throwing it out there as possible cause to research.
One case I've seen where an apparently unneeded index is explicitly referenced is where a scan is going to happen anyway so an index containing just the required columns is created so something smaller than the full table is scanned, but the query planner tries something else anyway (hitting other tables first and replacing the scan with a great many seeks in this table) that turns out to be more time consuming. This is usually a sign of bad query design (something non-sargable that could be made sargable) or just a miss-match of the data structure and what reports are wanted from it, though could indicate something that causes bad index stats to be likely, but without reference to the code you can't check that (and likely couldn't safely do anything about it anyway). It could also be something that is no longer needed, as it was put in place for an older version of SQL Server and newer releases have improved the query planner such that it wouldn't need the index hint to make the better choice.
Also, as pointed out in Dan's answer, someone could be using the terrible antipattern of trying to control ordering by index choice rather than an explicit ORDER BY, or has unknowingly relied upon the order produced by particular index use (without an explicit hint) where an explicit ORDER BY should really be given but has never been needed before (in this latter case, things may break similarly in future even if you put the original indexes back in, now might be the time to consider sun-setting and replacing that piece of software!).