[SalesForce] “FeedItem requires a filter by Id” exception despite filtering by ID

A client is getting an exception whenever they insert a FeedComment in their org. There is a trigger on FeedComment (api 25.0) which calls a static method in a class (api 26.0) to get a list of FeedItems.

The error is:

ns.myAppFeedComment: execution of AfterInsert

caused by: System.QueryException: Implementation restriction: FeedItem requires a filter by Id

Class.myApp.myAppFeedItemsHandler.getArchivedFeedItemsIdByFeedId: line 127, column 1
Trigger.myApp.myAppFeedComment: line 60, column 1

Here is the query. "tempIdSet" is the keySet of a map passed to getArchivedFeedItemsIdByFeedId as a parameter.

Set<Id> tempIdSet = idMap.keySet();

String query = 'Select RelatedRecordId, Id, Type, CreatedDate, CreatedById, CreatedBy.FirstName, CreatedBy.LastName,'+
                                    'ParentId, Body, Title, LinkUrl, InsertedById ,'+
                                    'ContentDescription,ContentType,ContentSize, ContentData, ContentFileName, CommentCount';


 if(myAppUtils.isCommunitiesEnabled()){

    communitiesEnabled = true;
    query+=', NetworkScope';
 }

query+=' From FeedItem i where i.Id in :tempIdSet';

List<Sobject> feedItems = Database.query(query);

The exception is obviously occurred when the query takes place. There are two things I don't understand.

1. I am filtering by ID. I am querying against a list of IDs, does it want me to use a single ID and put it in a for loop?
2. Secondly, this query is made every time a FeedComment is inserted and has worked for many clients without a problem – why would it suddenly fail? A Winter 14 bug? It can't be API Version since that hasn't changed.

It's difficult for me to debug fully since I don't have full access to the org, but any pointers would be great.

EDIT:

I reproduced with a System.runAs in a test with a standard user. If idMap contains [UserInfo.getUserId(), '123'] [null, '456']

Then I get the error.

The only problem with this hypothesis is that the map keys are populated from the FeedComment's FeedItemId in the After Insert trigger. Since FeedItemId is a required field, I don't see how it can be null.