I solved the problem. It had nothing to do with your plugin (which is a sweet plugin I must add).
The problem stemmed from a search filter I wrote to to exclude certain custom post types from user search queries.
If only I would have recognized this earlier, it would have saved me hours of SQL sniffing and debugging.