Si estoy realizando una regresión lineal, por ejemplo, y quito algunos puntos, ¿no seguiría ajustándose a los datos la misma línea/plano?
Aparte de los casos especiales no, OLS se ajusta a una línea que se crea sobre la base de la minimización de la suma de errores al cuadrado:
$$\min \sum e_i^2 = \min \sum (y_i-\hat{y_i})=\min \sum (y_i - \mathbf{x}_i^{\prime} \beta)^2 .$$
Si se eliminan algunas observaciones, es probable que cambie la función objetivo anterior, lo que hará que otra línea tenga el mejor ajuste a través de los datos (salvo en casos especiales, como cuando todas las observaciones están en una sola línea).
Si no es así, ¿no mostraría eso que los datos no tienen una relación lineal?
No necesariamente, se supone que existe una relación lineal entre las variables del "fondo", pero como no podemos observar directamente el proceso de generación de datos y siempre habrá algún término de perturbación aunque estemos seguros de que debería haber una relación lineal entre las dos variables, las observaciones no caerán necesariamente todas en una sola línea.
La no linealidad no puede detectarse sólo por el hecho de que la línea que se ajusta cambie cuando se eliminan algunos datos (aunque eso es un indicador de la solidez de un resultado: los resultados sólidos no deberían cambiar demasiado cuando se amplía/corta ligeramente la muestra). Sin embargo, se puede detectar la no linealidad de otras maneras. Por ejemplo, puede buscar patrones en el gráfico de residuos. Si el gráfico residual muestra algún patrón curvo, es un indicador de posible no linealidad. También existen pruebas rigurosas para detectar la no linealidad (como la prueba de Ramsey, etc.), pero repasar todas estas formas iría más allá del alcance de una respuesta de SE; puede leer más sobre ellas en libros de texto de econometría como Wooldridge Introductory Econometrics: A Modern Approach.