My trouble with Unicode cue sheets is partly rooted in my own confusion about all the Unicode formats and the (in my opinion) not very straight-forward handling of Unicode in my preferred editor UltraEdit-32.
For instance UltraEdit-32 always handles Unicode files, no matter whether they're UTF-8 or UTF-16, as UTF-16 internally. So when I switch to Hex view I will always see UTF-8 characters in double byte. Also whether BOM are present in the current files is kind of hidden, and changing the preferred setting whether newly created Unicode files will have a BOM only takes effect after restarting UltraEdit-32... additionally there are many "Conversion" methods accessible from the menu and UTF-16 is never explicitely mentioned, instead "Unicode" is used for it, whereas "UTF-8" stands for UTF-8...

I've asked a similar question before in the fb2k forum, but that post was full of errors and misconceptions I had at that time (and maybe still have) and it's not worth linking here...
But now I found a way to make sure that the CUE sheets are exactly saved in the way I want them to, when using "Save as..." instead of "Save" I can force a specific Unicode format including BOM status and even UTF-16 is mentioned in the File requester dialog...
So it is UTF-8 without BOM...? that can't be right.
When I save UTF-8 without BOM I get the error "could not enumerate tracks (Object not found) on:" (the first Unicode encoded character is in the file name of the image, in this case a "ú").
Saving an UTF-8 with a BOM works. foobar2000 accepts this file without a complaint.
And I just checked back with another Hex editor, since UE's hex view is unusable in combination with Unicode files (uses UTF-16 internally). When using the "Save as..." file requester, "UTF-8 NO BOM" and "UTF-8" (with BOM) are exactly the same, except for the BOM. So I guess therefore it's UTF-8 with BOM... I'll now check with Notepad++ and see how it actually saves those files, maybe it's not correct how UE-32 does it?