1. Yes.  It may take a long time, but eventually it will happen.
If v is reachable from s, eventually Modified-BFS(G,s) will visit v.


More explanation (you didn't need to give this level of detail):

Modified-BFS(G,s) basically explores all paths from s, in order of
their length.  Suppose there is a path from s to v of finite length,
say length L.  There can be only finitely many paths of length L or
less, so Modified-BFS(G,s) must eventually explore that path from
s to v.

More formally, consider the set P of all paths in G that start at s.
(There may be infinitely many such paths, or there may be finitely
many such paths, depending upon whether there are any cycles reachable
from s or not.)  Then there exists an enumeration p_1, p_2, p_3, ... 
of the paths in P, with two properties:
  (a) the paths are ordered by length, i.e., we have
      length(p_i) <= length(p_{i+1}) for every i=1.
  (b) Modified-BFS(G,s) appends nodes onto the queue in the order
      v_1, v_2, v_3, ..., where v_i denotes the vertex that p_i ends
      at.
If v is reachable from s, then there is some path of finite length
from s to v.  Say it is p_i.  Then we know that v_i = v, so that v
is the i-th item appended to the queue.  At that point the length of
the queue can't be any larger than i, so after at most i more iterations
of the while-loop, we will have removed v from the queue and visited v.
So every reachable vertex is eventually visited by this algorithm.

Note that this algorithm might not terminate, depending upon the
graph.  For instance, consider this graph:

    A ---> B
    ^      |
    |      v
    D <--- C

Modified-BFS will run forever on this graph, since the graph has
a cycle.  However it's still true that every vertex is eventually
reached.


2. No.  Each vertex could be visited multiple times -- possibly
a huge number of times.  I hope you noticed that Modified-BFS is
a terrible algorithm, because its running time could be ridiculously
large, even if there are no cycles in the graph.  The worst-case
running time could be exponential in |V|.  e.g.,

  A
 / \
B   C
 \ /
  D
 / \
E   F
 \ /
  G
 / \
H   I
 \ /
  J
 ...

where all edges point downwards.
D gets inserted into the queue 2 times; G gets inserted 4 times;
J gets inserted 8 times; and we can see that the number of times
That a node gets inserted is exponential in |V|.

You didn't need to provide this level of detail in your answer.


Comments:

You didn't need to give a precise analysis of the running time.
If you showed an example whose running time is exponential in |V|
or |E|, that's good enough for full credit.  Showing that the
running time could be at least c |V|^2 or at least c |E|^2 or at
least c |V| |E| (for some constant c) is also good enough to get
full credit, if you gave some reasonable explanation.

For instance, here is one way to see that the running time could be c
|V| |E| or worse, for some constant c (say, c = 1/2).  A vertex v is
inserted into the queue as many times as it has incoming edges.  This
means that each edge out of v is examined at least as many times as
there are edges into v.  The average in-degree can be as large as
|V|/2, depending on the graph.  This means that each edge might be
processed at least |V|/2 times on average, so the total running time
might be at least |V| |E|/2 or so.

Be careful, though.  This does not mean that the worst-case running
time of the algorithm is O(|V| |E|).  Actually, as the example above
shows, the running time could be much, much worse than that (it could
be exponential in |V|).  This is only a lower bound, so all you can
conclude is that the running time might be as slow as c |V| |E| or
slower.


Further explanation:

Consider the graph mentioned above (all edges point downwards):

  A
 / \
B   C
 \ /
  D
 / \
E   F
 \ /
  G
 / \
H   I
 \ /
  J
 ...

The number of times that a vertex v is inserted into the queue
is the number of different paths from s to v in the graph G.
That's also the number of times that v is removed from the queue.
Therefore, the number of iterations of the while-loop is the sum
of these numbers, over all vertices.

The example shown above illustrates that with |V|=3k+1 vertices, the
running time is at least 2^k = Theta(2^{|V|/3}), which is exponential
in n.

Here's another example.  Suppose that we have n vertices, numbered
1,2,3,..,n; and n(n-1)/2 edges, namely, an edge from vertex i to
vertex j, for every pair i,j with i < j.  It looks something like this:
           ____________
          /            \
         /              V
A ----> B ----> C ----> D  ...
|\              ^       ^
| \____________/        |
 \_____________________/

We can see that A is inserted into the queue once (and thus
removed from queue once).  When A is removed from the queue, B
is inserted.

So B is inserted into the queue once.  And this means B is removed
from the queue once.

C is added to the queue once when A is removed from the queue,
and once when B is removed from the queue.  So in total C is added
to the queue two times.  This also means that C is removed from the
queue two times.

D is added to the queue once when A is removed from the queue,
and we traverse the edge A-->D; it's added to the queue once when
B is removed from the queue, and we traverse the edge B-->D; and
D is added to the queue twice, once for each time when we remove
C from the queue and then traverse the edge C-->D.  So D is added
to the queue 1+1+2 = 4 times in total.  Thus D is removed from the
queue 4 times.

Similarly, E is added to the queue 1+1+2+4 = 8 times, and removed
from the queue 8 times.

Overall the i-th vertex is added to the queue 2^{i-1} times, for
i>1.  This means that the running time is at least 2^{n-1}, which
is exponential in |V|.


These problems are intended to illustrate why we mark vertices
and don't re-visit vertices that have been previously marked.  That
is an optimization that is crucial for the linear running time of
DFS and BFS.  Otherwise, we might end up re-visiting some vertices
a huge number of times, re-doing a tremendous amount of work for no
good reason, and blowing up the total running time.

These problems also illustrate why, in BFS, it's important to ensure
that if the node v is already in the queue, we don't add a second copy
of it to the queue.  Fortunately, marking each vertex when it's added
to the queue and never adding an already-marked vertex to the queue
suffices to ensure that the queue never contains more than one copy of
any vertex at any time.