SPQuery by no way will make your code slow, infact every other SharePoint article on net advice you to use SPQuery to gain Performance. To make things still more interesting GetItemByID internally use SPQuery to fetch the Item back to you,following is part of code taken from the GetItemByID function
SPQuery query = new SPQuery();
query.Query = "<Where><Eq><FieldRef Name=\"ID\"></FieldRef><Value Type=\"Integer\">" + id.ToString(CultureInfo.InvariantCulture) + "</Value></Eq></Where>";
Important to note here is SPQuery has a Internal property called SingleItemId which takes Id of the Item Id you want to fetch, further tracing of how it being used cannot be found as the call finally lands up in COM Object.
Being said that you have two options
Option 1:
Wrap your GetItemByID code inside the catch block and check for exception,if one occurs you can mark a flag to denote that Item Id is invalid and take action for it.
Option 2:Use SPQuery, you can test the time difference GetItemByID & using SPQuery, you will see that there is no and just a very very little time difference between two.