I did find a solution for the problem, I was using an SQL account for my linkedserver connections. When I changed it to use the "Be made using the current security context" option and setting up the manual spn (because I'm running the services under domain accounts) it is running correctly. This seems to fix the problem, still finding it strange that the query plans get messed up when changing the security context for the linked servers.