If the point $(x,y)$ is in a obtuse quadrant between the lines the problem is easily solved by enumerating the lattice points in a closed sphere of radius $\sqrt{2}$ about the intersection point so I will only consider the case that $(x,y)$ lies in a acute quadrant.

The problem can be converted to one that is very similar to inhomogeneous Diophantine approximation. I know of at least one algorithm that will definitely find the correct answer in $O\left(\tfrac{1}{\theta}\right)$ operations where $2\theta$ is the acute angle between the lines. The algorithm is a minor modification of that given on page 19 of [Vaughan Clarkson's thesis][1]. I am very confident that Cassels' algorithm (or a minor modification of it) will solve the problem in $O\left(1 + \log\tfrac{1}{\theta}\right)$ operations (page 34 of [1]), but I am not quite sure how to show it, or what modification needs to be made. Before I describe this, you need to know a little bit about inhomogeneous Diophantine approximation.

Let $\alpha$ and $\beta$ be real numbers. Define the function

$F(p,q) = |\alpha p - q - \beta|$.

The problem of inhomogeneous Diophantine approximation involves minimising $F(p,q)$ over integers $p$ and $q$ where $q$ is positive. The pair $(p, q)$ is called a *best approximation* if $F(p,q) < F(p',q')$ for all $q' < q$. The best approximations describe the minima found as $q$ and the magnitude of $p$ increase. The are various algorithms than can enumerate all of the best approximations. Two examples are the 'naive algorithm' (page 19 of [1]) and Cassel's algorithm (page 34 of [1]). The OP's problem is not exactly the same as this, but it is so similar that the algorithms (at least the naive algorithm) carry over.

Let our two lines be $\ell_1$ and $\ell_2$ and let $2\theta < \pi/2$ be the angle between them. It will be easier to describe the approach if we set the intersection of these lines to be at the origin and we look for the nearest point in the translated lattice $\mathbb{Z}^2 + t$ where $t$ is the appropriate translation. Define $\ell$ to be the unique line that passes through the origin and bisects the acute angle between $\ell_1$ and $\ell_2$. The angle between $\ell$ and $\ell_1$ and $\ell$ and $\ell_2$ is $\theta$. The problem can now be stated as:

"Find the point $x \in \mathbb{Z}^2 + t$ that is nearest to the origin such that the angle between $x$ and $\ell$ is less than or equal to $\theta$"

Let $A(x)$ denote the angle between $\ell$ and $x$. Our motivation is now very similar to that in Diophantine approximation. That is, find all of the best approximation for $A(x)$, our problem is solved by the best approximation that first yields $A(x) \leq \theta$. It so happens that $A(x)$ is a very similar function to $F(p,q)$, to give this some context I will say that $F(p,q)$ is, in a sense, computing an *inner product* between two vectors, whereas $A(x)$ is computing an angle. In this context it is not surprising that the algorithms for Diophantine approximation can be used. 

I will only consider the 'naive algorithm' and I'll just give some geometric insight as to its functionality, this should be enough to convince the majority. The 'naive algorithm' enumerates every point in $\mathbb{Z}^2 + t$ that is a nearest lattice point to any point in the line $\ell$. In other words it consecutively locates (starting from the origin) every lattice point in $\mathbb{Z}^2 + t$ whose Voronoi cell (in this case squares) intersect $\ell$. A picture might be useful

![alt text][2]


It is not at all difficult to devise an algorithm which does this, just start at the origin and check where $\ell$ next crosses a boundary of a Voronoi cell. It also easy to see that the points it locates are a super set of the best approximations for $A(x)$ and also $F(p,q)$. The first point that the algorithm finds such that $A(x) < \theta$ is the solution to the problem.

This algorithm is called 'naive' because it checks a lot of lattice points that are not best approximations. Cassels' algorithm improves this substantially for the function $F(p,q)$. It's likely that a similar improvement is possible for $A(x)$ and someone might wish to work it out.

The OP (particularly on stack overflow, but also here) seems to have thrown quite a number of red herrings into the problem statement (rather annoying). For example, knowledge of the point (x,y) does nothing other than tell you which quadrant you are looking in. The statement about it converting the problem to NP-complete rather than NP-hard doesn't make any sense. Also, the fact that the lines pass through integer points is irrelevant.


 [1]: http://www.itee.uq.edu.au/~vaughan/Publications/thesis.pdf
 [2]: http://www.itee.uq.edu.au/~robertm/pictures/linemathoverflow.svg